Merge branch 'master' into debug-merge-master

14 files changed, 213 insertions, 84 deletions

diff --git a/src/libutil/args.cc b/src/libutil/args.cc
index 69aa0d094..4b8c55686 100644
--- a/src/libutil/args.cc
+++ b/src/libutil/args.cc
@@ -127,11 +127,11 @@ bool Args::processFlag(Strings::iterator & pos, Strings::iterator end)
                 if (flag.handler.arity == ArityAny) break;
                 throw UsageError("flag '%s' requires %d argument(s)", name, flag.handler.arity);
             }
-            if (flag.completer)
-                if (auto prefix = needsCompletion(*pos)) {
-                    anyCompleted = true;
+            if (auto prefix = needsCompletion(*pos)) {
+                anyCompleted = true;
+                if (flag.completer)
                     flag.completer(n, *prefix);
-                }
+            }
             args.push_back(*pos++);
         }
         if (!anyCompleted)
@@ -146,6 +146,7 @@ bool Args::processFlag(Strings::iterator & pos, Strings::iterator end)
                     && hasPrefix(name, std::string(*prefix, 2)))
                     completions->add("--" + name, flag->description);
             }
+            return false;
         }
         auto i = longFlags.find(std::string(*pos, 2));
         if (i == longFlags.end()) return false;
@@ -187,10 +188,12 @@ bool Args::processArgs(const Strings & args, bool finish)
     {
         std::vector<std::string> ss;
         for (const auto &[n, s] : enumerate(args)) {
-            ss.push_back(s);
-            if (exp.completer)
-                if (auto prefix = needsCompletion(s))
+            if (auto prefix = needsCompletion(s)) {
+                ss.push_back(*prefix);
+                if (exp.completer)
                     exp.completer(n, *prefix);
+            } else
+                ss.push_back(s);
         }
         exp.handler.fun(ss);
         expectedArgs.pop_front();
@@ -279,21 +282,22 @@ static void _completePath(std::string_view prefix, bool onlyDirs)
 {
     completionType = ctFilenames;
     glob_t globbuf;
-    int flags = GLOB_NOESCAPE | GLOB_TILDE;
+    int flags = GLOB_NOESCAPE;
     #ifdef GLOB_ONLYDIR
     if (onlyDirs)
         flags |= GLOB_ONLYDIR;
     #endif
-    if (glob((std::string(prefix) + "*").c_str(), flags, nullptr, &globbuf) == 0) {
+    // using expandTilde here instead of GLOB_TILDE(_CHECK) so that ~<Tab> expands to /home/user/
+    if (glob((expandTilde(prefix) + "*").c_str(), flags, nullptr, &globbuf) == 0) {
         for (size_t i = 0; i < globbuf.gl_pathc; ++i) {
             if (onlyDirs) {
-                auto st = lstat(globbuf.gl_pathv[i]);
+                auto st = stat(globbuf.gl_pathv[i]);
                 if (!S_ISDIR(st.st_mode)) continue;
             }
             completions->add(globbuf.gl_pathv[i]);
         }
-        globfree(&globbuf);
     }
+    globfree(&globbuf);
 }
 
 void completePath(size_t, std::string_view prefix)
@@ -322,11 +326,6 @@ MultiCommand::MultiCommand(const Commands & commands_)
         .optional = true,
         .handler = {[=](std::string s) {
             assert(!command);
-            if (auto prefix = needsCompletion(s)) {
-                for (auto & [name, command] : commands)
-                    if (hasPrefix(name, *prefix))
-                        completions->add(name);
-            }
             auto i = commands.find(s);
             if (i == commands.end()) {
                 std::set<std::string> commandNames;
@@ -337,6 +336,11 @@ MultiCommand::MultiCommand(const Commands & commands_)
             }
             command = {s, i->second()};
             command->second->parent = this;
+        }},
+        .completer = {[&](size_t, std::string_view prefix) {
+            for (auto & [name, command] : commands)
+                if (hasPrefix(name, prefix))
+                    completions->add(name);
         }}
     });
 
diff --git a/src/libutil/chunked-vector.hh b/src/libutil/chunked-vector.hh
new file mode 100644
index 000000000..0a4f0b400
--- /dev/null
+++ b/src/libutil/chunked-vector.hh
@@ -0,0 +1,68 @@
+#pragma once
+
+#include <cstdint>
+#include <cstdlib>
+#include <vector>
+#include <limits>
+
+namespace nix {
+
+/* Provides an indexable container like vector<> with memory overhead
+   guarantees like list<> by allocating storage in chunks of ChunkSize
+   elements instead of using a contiguous memory allocation like vector<>
+   does. Not using a single vector that is resized reduces memory overhead
+   on large data sets by on average (growth factor)/2, mostly
+   eliminates copies within the vector during resizing, and provides stable
+   references to its elements. */
+template<typename T, size_t ChunkSize>
+class ChunkedVector {
+private:
+    uint32_t size_ = 0;
+    std::vector<std::vector<T>> chunks;
+
+    /* keep this out of the ::add hot path */
+    [[gnu::noinline]]
+    auto & addChunk()
+    {
+        if (size_ >= std::numeric_limits<uint32_t>::max() - ChunkSize)
+            abort();
+        chunks.emplace_back();
+        chunks.back().reserve(ChunkSize);
+        return chunks.back();
+    }
+
+public:
+    ChunkedVector(uint32_t reserve)
+    {
+        chunks.reserve(reserve);
+        addChunk();
+    }
+
+    uint32_t size() const { return size_; }
+
+    std::pair<T &, uint32_t> add(T value)
+    {
+        const auto idx = size_++;
+        auto & chunk = [&] () -> auto & {
+            if (auto & back = chunks.back(); back.size() < ChunkSize)
+                return back;
+            return addChunk();
+        }();
+        auto & result = chunk.emplace_back(std::move(value));
+        return {result, idx};
+    }
+
+    const T & operator[](uint32_t idx) const
+    {
+        return chunks[idx / ChunkSize][idx % ChunkSize];
+    }
+
+    template<typename Fn>
+    void forEach(Fn fn) const
+    {
+        for (const auto & c : chunks)
+            for (const auto & e : c)
+                fn(e);
+    }
+};
+}
diff --git a/src/libutil/error.hh b/src/libutil/error.hh
index e31311c80..6eb80fb9e 100644
--- a/src/libutil/error.hh
+++ b/src/libutil/error.hh
@@ -87,11 +87,7 @@ struct ErrPos {
         origin = pos.origin;
         line = pos.line;
         column = pos.column;
-        // is file symbol null?
-        if (pos.file.set())
-            file = pos.file;
-        else
-            file = "";
+        file = pos.file;
         return *this;
     }
 
diff --git a/src/libutil/experimental-features.cc b/src/libutil/experimental-features.cc
index e033a4116..df37edf57 100644
--- a/src/libutil/experimental-features.cc
+++ b/src/libutil/experimental-features.cc
@@ -58,4 +58,18 @@ std::ostream & operator <<(std::ostream & str, const ExperimentalFeature & featu
     return str << showExperimentalFeature(feature);
 }
 
+void to_json(nlohmann::json& j, const ExperimentalFeature& feature) {
+    j = showExperimentalFeature(feature);
+}
+
+void from_json(const nlohmann::json& j, ExperimentalFeature& feature) {
+    const std::string input = j;
+    const auto parsed = parseExperimentalFeature(input);
+
+    if (parsed.has_value())
+        feature = *parsed;
+    else
+        throw Error("Unknown experimental feature '%s' in JSON input", input);
+}
+
 }
diff --git a/src/libutil/experimental-features.hh b/src/libutil/experimental-features.hh
index 266e41a22..a6d080094 100644
--- a/src/libutil/experimental-features.hh
+++ b/src/libutil/experimental-features.hh
@@ -51,4 +51,11 @@ public:
     MissingExperimentalFeature(ExperimentalFeature);
 };
 
+/**
+ * Semi-magic conversion to and from json.
+ * See the nlohmann/json readme for more details.
+ */
+void to_json(nlohmann::json&, const ExperimentalFeature&);
+void from_json(const nlohmann::json&, ExperimentalFeature&);
+
 }
diff --git a/src/libutil/fmt.hh b/src/libutil/fmt.hh
index 0821b3b74..7664e5c04 100644
--- a/src/libutil/fmt.hh
+++ b/src/libutil/fmt.hh
@@ -2,7 +2,6 @@
 
 #include <boost/format.hpp>
 #include <string>
-#include <regex>
 #include "ansicolor.hh"
 
 
@@ -155,15 +154,4 @@ inline hintformat hintfmt(std::string plain_string)
     return hintfmt("%s", normaltxt(plain_string));
 }
 
-/* Highlight all the given matches in the given string `s` by wrapping
-   them between `prefix` and `postfix`.
-
-   If some matches overlap, then their union will be wrapped rather
-   than the individual matches. */
-std::string hiliteMatches(
-    std::string_view s,
-    std::vector<std::smatch> matches,
-    std::string_view prefix,
-    std::string_view postfix);
-
 }
diff --git a/src/libutil/fmt.cc b/src/libutil/hilite.cc
index 3dd93d73e..a5991ca39 100644
--- a/src/libutil/fmt.cc
+++ b/src/libutil/hilite.cc
@@ -1,6 +1,4 @@
-#include "fmt.hh"
-
-#include <regex>
+#include "hilite.hh"
 
 namespace nix {
 
diff --git a/src/libutil/hilite.hh b/src/libutil/hilite.hh
new file mode 100644
index 000000000..f8bdbfc55
--- /dev/null
+++ b/src/libutil/hilite.hh
@@ -0,0 +1,20 @@
+#pragma once
+
+#include <regex>
+#include <vector>
+#include <string>
+
+namespace nix {
+
+/* Highlight all the given matches in the given string `s` by wrapping
+   them between `prefix` and `postfix`.
+
+   If some matches overlap, then their union will be wrapped rather
+   than the individual matches. */
+std::string hiliteMatches(
+    std::string_view s,
+    std::vector<std::smatch> matches,
+    std::string_view prefix,
+    std::string_view postfix);
+
+}
diff --git a/src/libutil/ref.hh b/src/libutil/ref.hh
index 347b81f73..f9578afc7 100644
--- a/src/libutil/ref.hh
+++ b/src/libutil/ref.hh
@@ -99,47 +99,4 @@ make_ref(Args&&... args)
     return ref<T>(p);
 }
 
-
-/* A non-nullable pointer.
-   This is similar to a C++ "& reference", but mutable.
-   This is similar to ref<T> but backed by a regular pointer instead of a smart pointer.
- */
-template<typename T>
-class ptr {
-private:
-    T * p;
-
-public:
-    ptr<T>(const ptr<T> & r)
-        : p(r.p)
-    { }
-
-    explicit ptr<T>(T * p)
-        : p(p)
-    {
-        if (!p)
-            throw std::invalid_argument("null pointer cast to ptr");
-    }
-
-    T* operator ->() const
-    {
-        return &*p;
-    }
-
-    T& operator *() const
-    {
-        return *p;
-    }
-
-    bool operator == (const ptr<T> & other) const
-    {
-        return p == other.p;
-    }
-
-    bool operator != (const ptr<T> & other) const
-    {
-        return p != other.p;
-    }
-};
-
 }
diff --git a/src/libutil/tests/chunked-vector.cc b/src/libutil/tests/chunked-vector.cc
new file mode 100644
index 000000000..868d11f6f
--- /dev/null
+++ b/src/libutil/tests/chunked-vector.cc
@@ -0,0 +1,54 @@
+#include "chunked-vector.hh"
+
+#include <gtest/gtest.h>
+
+namespace nix {
+    TEST(ChunkedVector, InitEmpty) {
+        auto v = ChunkedVector<int, 2>(100);
+        ASSERT_EQ(v.size(), 0);
+    }
+
+    TEST(ChunkedVector, GrowsCorrectly) {
+        auto v = ChunkedVector<int, 2>(100);
+        for (auto i = 1; i < 20; i++) {
+            v.add(i);
+            ASSERT_EQ(v.size(), i);
+        }
+    }
+
+    TEST(ChunkedVector, AddAndGet) {
+        auto v = ChunkedVector<int, 2>(100);
+        for (auto i = 1; i < 20; i++) {
+            auto [i2, idx] = v.add(i);
+            auto & i3 = v[idx];
+            ASSERT_EQ(i, i2);
+            ASSERT_EQ(&i2, &i3);
+        }
+    }
+
+    TEST(ChunkedVector, ForEach) {
+        auto v = ChunkedVector<int, 2>(100);
+        for (auto i = 1; i < 20; i++) {
+            v.add(i);
+        }
+        int count = 0;
+        v.forEach([&count](int elt) {
+            count++;
+        });
+        ASSERT_EQ(count, v.size());
+    }
+
+    TEST(ChunkedVector, OverflowOK) {
+        // Similar to the AddAndGet, but intentionnally use a small
+        // initial ChunkedVector to force it to overflow
+        auto v = ChunkedVector<int, 2>(2);
+        for (auto i = 1; i < 20; i++) {
+            auto [i2, idx] = v.add(i);
+            auto & i3 = v[idx];
+            ASSERT_EQ(i, i2);
+            ASSERT_EQ(&i2, &i3);
+        }
+    }
+
+}
+
diff --git a/src/libutil/tests/fmt.cc b/src/libutil/tests/hilite.cc
index 33772162c..1ff5980d5 100644
--- a/src/libutil/tests/fmt.cc
+++ b/src/libutil/tests/hilite.cc
@@ -1,9 +1,7 @@
-#include "fmt.hh"
+#include "hilite.hh"
 
 #include <gtest/gtest.h>
 
-#include <regex>
-
 namespace nix {
 /* ----------- tests for fmt.hh -------------------------------------------------*/
 
diff --git a/src/libutil/types.hh b/src/libutil/types.hh
index 00ba567c6..6bcbd7e1d 100644
--- a/src/libutil/types.hh
+++ b/src/libutil/types.hh
@@ -5,6 +5,7 @@
 #include <list>
 #include <set>
 #include <string>
+#include <limits>
 #include <map>
 #include <variant>
 #include <vector>
diff --git a/src/libutil/util.cc b/src/libutil/util.cc
index c075a14b4..b49c1e466 100644
--- a/src/libutil/util.cc
+++ b/src/libutil/util.cc
@@ -198,6 +198,17 @@ std::string_view baseNameOf(std::string_view path)
 }
 
 
+std::string expandTilde(std::string_view path)
+{
+    // TODO: expand ~user ?
+    auto tilde = path.substr(0, 2);
+    if (tilde == "~/" || tilde == "~")
+        return getHome() + std::string(path.substr(1));
+    else
+        return std::string(path);
+}
+
+
 bool isInDir(std::string_view path, std::string_view dir)
 {
     return path.substr(0, 1) == "/"
@@ -213,6 +224,15 @@ bool isDirOrInDir(std::string_view path, std::string_view dir)
 }
 
 
+struct stat stat(const Path & path)
+{
+    struct stat st;
+    if (stat(path.c_str(), &st))
+        throw SysError("getting status of '%1%'", path);
+    return st;
+}
+
+
 struct stat lstat(const Path & path)
 {
     struct stat st;
@@ -1062,7 +1082,7 @@ std::string runProgram(Path program, bool searchPath, const Strings & args,
     auto res = runProgram(RunOptions {.program = program, .searchPath = searchPath, .args = args, .input = input});
 
     if (!statusOk(res.first))
-        throw ExecError(res.first, fmt("program '%1%' %2%", program, statusToString(res.first)));
+        throw ExecError(res.first, "program '%1%' %2%", program, statusToString(res.first));
 
     return res.second;
 }
@@ -1190,7 +1210,7 @@ void runProgram2(const RunOptions & options)
     if (source) promise.get_future().get();
 
     if (status)
-        throw ExecError(status, fmt("program '%1%' %2%", options.program, statusToString(status)));
+        throw ExecError(status, "program '%1%' %2%", options.program, statusToString(status));
 }
 
 
diff --git a/src/libutil/util.hh b/src/libutil/util.hh
index 20591952d..a1d0e0e6b 100644
--- a/src/libutil/util.hh
+++ b/src/libutil/util.hh
@@ -68,6 +68,9 @@ Path dirOf(const PathView path);
    following the final `/' (trailing slashes are removed). */
 std::string_view baseNameOf(std::string_view path);
 
+/* Perform tilde expansion on a path. */
+std::string expandTilde(std::string_view path);
+
 /* Check whether 'path' is a descendant of 'dir'. Both paths must be
    canonicalized. */
 bool isInDir(std::string_view path, std::string_view dir);
@@ -77,6 +80,7 @@ bool isInDir(std::string_view path, std::string_view dir);
 bool isDirOrInDir(std::string_view path, std::string_view dir);
 
 /* Get status of `path'. */
+struct stat stat(const Path & path);
 struct stat lstat(const Path & path);
 
 /* Return true iff the given path exists. */