Merge pull request #7348 from thufschmitt/dont-use-vlas

Remove the usage of VLAs in the code

(cherry picked from commit ac4431e9d016e62fb5dc9ae36833bd0c6cdadeec)
Change-Id: Ifbf5fbfc2e27122362a2aaea4b62c7cf3ca46b1a

5 files changed, 70 insertions, 20 deletions

diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index b1268bb12..e98280f33 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -1,6 +1,7 @@
 #include "eval.hh"
 #include "eval-settings.hh"
 #include "hash.hh"
+#include "primops.hh"
 #include "types.hh"
 #include "util.hh"
 #include "store-api.hh"
@@ -38,6 +39,7 @@
 #include <boost/coroutine2/coroutine.hpp>
 #include <boost/coroutine2/protected_fixedsize_stack.hpp>
 #include <boost/context/stack_context.hpp>
+#include <boost/container/small_vector.hpp>
 
 #endif
 
@@ -703,6 +705,23 @@ void EvalState::addConstant(const std::string & name, Value * v, Constant info)
 }
 
 
+void PrimOp::check()
+{
+    if (arity > maxPrimOpArity) {
+        throw Error("primop arity must not exceed %1%", maxPrimOpArity);
+    }
+}
+
+
+void Value::mkPrimOp(PrimOp * p)
+{
+    p->check();
+    clearValue();
+    internalType = tPrimOp;
+    primOp = p;
+}
+
+
 Value * EvalState::addPrimOp(PrimOp && primOp)
 {
     /* Hack to make constants lazy: turn them into a application of
@@ -1683,7 +1702,7 @@ void EvalState::callFunction(Value & fun, size_t nrArgs, Value * * args, Value &
                 /* We have all the arguments, so call the primop with
                    the previous and new arguments. */
 
-                Value * vArgs[arity];
+                Value * vArgs[maxPrimOpArity];
                 auto n = argsDone;
                 for (Value * arg = &vCur; arg->isPrimOpApp(); arg = arg->primOpApp.left)
                     vArgs[--n] = arg->primOpApp.right;
@@ -1740,11 +1759,17 @@ void ExprCall::eval(EvalState & state, Env & env, Value & v)
     Value vFun;
     fun->eval(state, env, vFun);
 
-    Value * vArgs[args.size()];
+    // Empirical arity of Nixpkgs lambdas by regex e.g. ([a-zA-Z]+:(\s|(/\*.*\/)|(#.*\n))*){5}
+    // 2: over 4000
+    // 3: about 300
+    // 4: about 60
+    // 5: under 10
+    // This excluded attrset lambdas (`{...}:`). Contributions of mixed lambdas appears insignificant at ~150 total.
+    boost::container::small_vector<Value *, 4> vArgs(args.size());
     for (size_t i = 0; i < args.size(); ++i)
         vArgs[i] = args[i]->maybeThunk(state, env);
 
-    state.callFunction(vFun, args.size(), vArgs, v, pos);
+    state.callFunction(vFun, args.size(), vArgs.data(), v, pos);
 }
 
 
@@ -1983,8 +2008,8 @@ void ExprConcatStrings::eval(EvalState & state, Env & env, Value & v)
         return result;
     };
 
-    Value values[es->size()];
-    Value * vTmpP = values;
+    boost::container::small_vector<Value, conservativeStackReservation> values(es->size());
+    Value * vTmpP = values.data();
 
     for (auto & [i_pos, i] : *es) {
         Value & vTmp = *vTmpP++;
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index 42dd73d11..4425efbca 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -18,6 +18,12 @@
 
 namespace nix {
 
+/**
+ * We put a limit on primop arity because it lets us use a fixed size array on
+ * the stack. 8 is already an impractical number of arguments. Use an attrset
+ * argument for such overly complicated functions.
+ */
+constexpr size_t maxPrimOpArity = 8;
 
 class Store;
 class EvalState;
@@ -69,6 +75,12 @@ struct PrimOp
      * Optional experimental for this to be gated on.
      */
     std::optional<ExperimentalFeature> experimentalFeature;
+
+    /**
+     * Validity check to be performed by functions that introduce primops,
+     * such as RegisterPrimOp() and Value::mkPrimOp().
+     */
+    void check();
 };
 
 /**
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index fca20358a..44a97461a 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -28,7 +28,6 @@
 
 #include <cmath>
 
-
 namespace nix {
 
 
@@ -2547,6 +2546,7 @@ static void prim_removeAttrs(EvalState & state, const PosIdx pos, Value * * args
     /* Get the attribute names to be removed.
        We keep them as Attrs instead of Symbols so std::set_difference
        can be used to remove them from attrs[0]. */
+    // 64: large enough to fit the attributes of a derivation
     boost::container::small_vector<Attr, 64> names;
     names.reserve(args[1]->listSize());
     for (auto elem : args[1]->listItems()) {
@@ -2726,8 +2726,8 @@ static void prim_catAttrs(EvalState & state, const PosIdx pos, Value * * args, V
     auto attrName = state.symbols.create(state.forceStringNoCtx(*args[0], pos, "while evaluating the first argument passed to builtins.catAttrs"));
     state.forceList(*args[1], pos, "while evaluating the second argument passed to builtins.catAttrs");
 
-    Value * res[args[1]->listSize()];
-    unsigned int found = 0;
+    boost::container::small_vector<Value *, nonRecursiveStackReservation> res(args[1]->listSize());
+    size_t found = 0;
 
     for (auto v2 : args[1]->listItems()) {
         state.forceAttrs(*v2, pos, "while evaluating an element in the list passed as second argument to builtins.catAttrs");
@@ -3061,9 +3061,8 @@ static void prim_filter(EvalState & state, const PosIdx pos, Value * * args, Val
 
     state.forceFunction(*args[0], pos, "while evaluating the first argument passed to builtins.filter");
 
-    // FIXME: putting this on the stack is risky.
-    Value * vs[args[1]->listSize()];
-    unsigned int k = 0;
+    boost::container::small_vector<Value *, nonRecursiveStackReservation> vs(args[1]->listSize());
+    size_t k = 0;
 
     bool same = true;
     for (unsigned int n = 0; n < args[1]->listSize(); ++n) {
@@ -3188,10 +3187,14 @@ static void anyOrAll(bool any, EvalState & state, const PosIdx pos, Value * * ar
     state.forceFunction(*args[0], pos, std::string("while evaluating the first argument passed to builtins.") + (any ? "any" : "all"));
     state.forceList(*args[1], pos, std::string("while evaluating the second argument passed to builtins.") + (any ? "any" : "all"));
 
+    std::string_view errorCtx = any
+        ? "while evaluating the return value of the function passed to builtins.any"
+        : "while evaluating the return value of the function passed to builtins.all";
+
     Value vTmp;
     for (auto elem : args[1]->listItems()) {
         state.callFunction(*args[0], *elem, vTmp, pos);
-        bool res = state.forceBool(vTmp, pos, std::string("while evaluating the return value of the function passed to builtins.") + (any ? "any" : "all"));
+        bool res = state.forceBool(vTmp, pos, errorCtx);
         if (res == any) {
             v.mkBool(any);
             return;
@@ -3447,7 +3450,7 @@ static void prim_concatMap(EvalState & state, const PosIdx pos, Value * * args,
     state.forceList(*args[1], pos, "while evaluating the second argument passed to builtins.concatMap");
     auto nrLists = args[1]->listSize();
 
-    Value lists[nrLists];
+    boost::container::small_vector<Value, conservativeStackReservation> lists(nrLists);
     size_t len = 0;
 
     for (unsigned int n = 0; n < nrLists; ++n) {
diff --git a/src/libexpr/primops.hh b/src/libexpr/primops.hh
index 930e7f32a..45486608f 100644
--- a/src/libexpr/primops.hh
+++ b/src/libexpr/primops.hh
@@ -8,6 +8,22 @@
 
 namespace nix {
 
+/**
+ * For functions where we do not expect deep recursion, we can use a sizable
+ * part of the stack a free allocation space.
+ *
+ * Note: this is expected to be multiplied by sizeof(Value), or about 24 bytes.
+ */
+constexpr size_t nonRecursiveStackReservation = 128;
+
+/**
+ * Functions that maybe applied to self-similar inputs, such as concatMap on a
+ * tree, should reserve a smaller part of the stack for allocation.
+ *
+ * Note: this is expected to be multiplied by sizeof(Value), or about 24 bytes.
+ */
+constexpr size_t conservativeStackReservation = 16;
+
 struct RegisterPrimOp
 {
     typedef std::vector<PrimOp> PrimOps;
diff --git a/src/libexpr/value.hh b/src/libexpr/value.hh
index c44683e50..ec7d82a64 100644
--- a/src/libexpr/value.hh
+++ b/src/libexpr/value.hh
@@ -349,13 +349,7 @@ public:
         // Value will be overridden anyways
     }
 
-    inline void mkPrimOp(PrimOp * p)
-    {
-        clearValue();
-        internalType = tPrimOp;
-        primOp = p;
-    }
-
+    void mkPrimOp(PrimOp * p);
 
     inline void mkPrimOpApp(Value * l, Value * r)
     {