refactor(3p/nix/libexpr): Back Nix lists with std::vector r/1377

This change does away with the previous special-casing of lists of
certain element sizes, and the use of raw C-style arrays.

Lists are now backed by a std::vector of nix::Value*, which uses the
traceable GC allocator.

This change is unfortunately quite noisy because the accessor methods
were updated/removed accordingly, so all callsites of Nix-related
lists have changed.

For some operations in primops.cc where keeping the previous code
structure would have been more difficult with a "proper" vector, the
implementation has been replaced with std::vector methods. For
example, list concatenation now uses appropriate range inserts.

Anecdotally the performance of this is about equal, to even slightly
better, than the previous implementation.

All language tests pass and the depot paths I've used for testing
still evaluate.

Change-Id: Ib5eca6c0207429cb323a330c838c3a2200b2c693
Reviewed-on: https://cl.tvl.fyi/c/depot/+/1266
Tested-by: BuildkiteCI
Reviewed-by: isomer <isomer@tvl.fyi>
Reviewed-by: Kane York <rikingcoding@gmail.com>
Reviewed-by: glittershark <grfn@gws.fyi>

16 files changed, 163 insertions, 231 deletions

diff --git a/third_party/nix/src/libexpr/attr-path.cc b/third_party/nix/src/libexpr/attr-path.cc
index e366f18575..a267e82b6e 100644
--- a/third_party/nix/src/libexpr/attr-path.cc
+++ b/third_party/nix/src/libexpr/attr-path.cc
@@ -99,7 +99,7 @@ Value* findAlongAttrPath(EvalState& state, const std::string& attrPath,
             attrIndex % attrPath);
       }
 
-      v = v->listElems()[attrIndex];
+      v = (*v->list)[attrIndex];
     }
   }
 
diff --git a/third_party/nix/src/libexpr/eval.cc b/third_party/nix/src/libexpr/eval.cc
index 16e6907214..f35f56c83c 100644
--- a/third_party/nix/src/libexpr/eval.cc
+++ b/third_party/nix/src/libexpr/eval.cc
@@ -97,12 +97,10 @@ static void printValue(std::ostream& str, std::set<const Value*>& active,
       str << "}";
       break;
     }
-    case tList1:
-    case tList2:
-    case tListN:
+    case tList:
       str << "[ ";
       for (unsigned int n = 0; n < v.listSize(); ++n) {
-        printValue(str, active, *v.listElems()[n]);
+        printValue(str, active, *(*v.list)[n]);
         str << " ";
       }
       str << "]";
@@ -162,9 +160,7 @@ std::string showType(const Value& v) {
       return "null";
     case tAttrs:
       return "a set";
-    case tList1:
-    case tList2:
-    case tListN:
+    case tList:
       return "a list";
     case tThunk:
       return "a thunk";
@@ -641,19 +637,15 @@ Env& EvalState::allocEnv(size_t size) {
   return *env;
 }
 
-void EvalState::mkList(Value& v, size_t size) {
+void EvalState::mkList(Value& v, NixList* list) {
   clearValue(v);
-  if (size == 1) {
-    v.type = tList1;
-  } else if (size == 2) {
-    v.type = tList2;
-  } else {
-    v.type = tListN;
-    v.bigList.size = size;
-    v.bigList.elems =
-        size != 0u ? (Value**)allocBytes(size * sizeof(Value*)) : nullptr;
-  }
-  nrListElems += size;
+  v.type = tList;
+  v.list = list;
+  nrListElems += list->size();
+}
+
+void EvalState::mkList(Value& v, size_t size) {
+  EvalState::mkList(v, new (GC) NixList(size));
 }
 
 unsigned long nrThunks = 0;
@@ -877,7 +869,7 @@ void ExprLet::eval(EvalState& state, Env& env, Value& v) {
 void ExprList::eval(EvalState& state, Env& env, Value& v) {
   state.mkList(v, elems.size());
   for (size_t n = 0; n < elems.size(); ++n) {
-    v.listElems()[n] = elems[n]->maybeThunk(state, env);
+    (*v.list)[n] = elems[n]->maybeThunk(state, env);
   }
 }
 
@@ -1252,39 +1244,21 @@ void ExprOpConcatLists::eval(EvalState& state, Env& env, Value& v) {
   e1->eval(state, env, v1);
   Value v2;
   e2->eval(state, env, v2);
-  Value* lists[2] = {&v1, &v2};
-  state.concatLists(v, 2, lists, pos);
+  state.concatLists(v, {&v1, &v2}, pos);
 }
 
-void EvalState::concatLists(Value& v, size_t nrLists, Value** lists,
-                            const Pos& pos) {
+void EvalState::concatLists(Value& v, const NixList& lists, const Pos& pos) {
   nrListConcats++;
 
-  Value* nonEmpty = nullptr;
-  size_t len = 0;
-  for (size_t n = 0; n < nrLists; ++n) {
-    forceList(*lists[n], pos);
-    auto l = lists[n]->listSize();
-    len += l;
-    if (l != 0u) {
-      nonEmpty = lists[n];
-    }
-  }
+  auto outlist = new (GC) NixList();
 
-  if ((nonEmpty != nullptr) && len == nonEmpty->listSize()) {
-    v = *nonEmpty;
-    return;
+  size_t len = 0;
+  for (Value* list : lists) {
+    forceList(*list, pos);
+    outlist->insert(outlist->end(), list->list->begin(), list->list->end());
   }
 
-  mkList(v, len);
-  auto out = v.listElems();
-  for (size_t n = 0, pos = 0; n < nrLists; ++n) {
-    auto l = lists[n]->listSize();
-    if (l != 0u) {
-      memcpy(out + pos, lists[n]->listElems(), l * sizeof(Value*));
-    }
-    pos += l;
-  }
+  mkList(v, outlist);
 }
 
 void ExprConcatStrings::eval(EvalState& state, Env& env, Value& v) {
@@ -1383,7 +1357,7 @@ void EvalState::forceValueDeep(Value& v) {
       }
     } else if (v.isList()) {
       for (size_t n = 0; n < v.listSize(); ++n) {
-        recurse(*v.listElems()[n]);
+        recurse(*(*v.list)[n]);
       }
     }
   };
@@ -1563,12 +1537,11 @@ std::string EvalState::coerceToString(const Pos& pos, Value& v,
     if (v.isList()) {
       std::string result;
       for (size_t n = 0; n < v.listSize(); ++n) {
-        result += coerceToString(pos, *v.listElems()[n], context, coerceMore,
+        result += coerceToString(pos, *(*v.list)[n], context, coerceMore,
                                  copyToStore);
         if (n < v.listSize() - 1
             /* !!! not quite correct */
-            && (!v.listElems()[n]->isList() ||
-                v.listElems()[n]->listSize() != 0)) {
+            && (!(*v.list)[n]->isList() || (*v.list)[n]->listSize() != 0)) {
           result += " ";
         }
       }
@@ -1653,14 +1626,12 @@ bool EvalState::eqValues(Value& v1, Value& v2) {
     case tNull:
       return true;
 
-    case tList1:
-    case tList2:
-    case tListN:
+    case tList:
       if (v1.listSize() != v2.listSize()) {
         return false;
       }
       for (size_t n = 0; n < v1.listSize(); ++n) {
-        if (!eqValues(*v1.listElems()[n], *v2.listElems()[n])) {
+        if (!eqValues(*(*v1.list)[n], *(*v2.list)[n])) {
           return false;
         }
       }
@@ -1883,14 +1854,12 @@ size_t valueSize(Value& v) {
           }
         }
         break;
-      case tList1:
-      case tList2:
-      case tListN:
-        if (seen.find(v.listElems()) == seen.end()) {
-          seen.insert(v.listElems());
+      case tList:
+        if (seen.find(v.list) == seen.end()) {
+          seen.insert(v.list);
           sz += v.listSize() * sizeof(Value*);
           for (size_t n = 0; n < v.listSize(); ++n) {
-            sz += doValue(*v.listElems()[n]);
+            sz += doValue(*(*v.list)[n]);
           }
         }
         break;
diff --git a/third_party/nix/src/libexpr/eval.hh b/third_party/nix/src/libexpr/eval.hh
index 3da0961b6f..3e875fa811 100644
--- a/third_party/nix/src/libexpr/eval.hh
+++ b/third_party/nix/src/libexpr/eval.hh
@@ -260,12 +260,19 @@ class EvalState {
 
   Value* allocAttr(Value& vAttrs, const Symbol& name);
 
-  void mkList(Value& v, size_t size);
+  // Create a list value from the specified vector.
+  void mkList(Value& v, NixList* list);
+
+  // Create a list value, allocating as many elements as specified in
+  // size. This is used for the many cases in this codebase where
+  // assignment happens into the preallocated list.
+  void mkList(Value& v, size_t size = 0);
+
   void mkAttrs(Value& v, size_t capacity);
   void mkThunk_(Value& v, Expr* expr);
   void mkPos(Value& v, Pos* pos);
 
-  void concatLists(Value& v, size_t nrLists, Value** lists, const Pos& pos);
+  void concatLists(Value& v, const NixList& lists, const Pos& pos);
 
   /* Print statistics. */
   void printStats();
diff --git a/third_party/nix/src/libexpr/get-drvs.cc b/third_party/nix/src/libexpr/get-drvs.cc
index 33bded2fa2..1d8fe1efa0 100644
--- a/third_party/nix/src/libexpr/get-drvs.cc
+++ b/third_party/nix/src/libexpr/get-drvs.cc
@@ -99,8 +99,8 @@ DrvInfo::Outputs DrvInfo::queryOutputs(bool onlyOutputsToInstall) {
       /* For each output... */
       for (unsigned int j = 0; j < i->second.value->listSize(); ++j) {
         /* Evaluate the corresponding set. */
-        std::string name = state->forceStringNoCtx(
-            *i->second.value->listElems()[j], *i->second.pos);
+        std::string name = state->forceStringNoCtx(*(*i->second.value->list)[j],
+                                                   *i->second.pos);
         Bindings::iterator out = attrs->find(state->symbols.Create(name));
         if (out == attrs->end()) {
           continue;  // FIXME: throw error?
@@ -136,12 +136,12 @@ DrvInfo::Outputs DrvInfo::queryOutputs(bool onlyOutputsToInstall) {
     throw errMsg;
   }
   Outputs result;
-  for (auto i = outTI->listElems(); i != outTI->listElems() + outTI->listSize();
-       ++i) {
-    if ((*i)->type != tString) {
+
+  for (Value* i : *outTI->list) {
+    if (i->type != tString) {
       throw errMsg;
     }
-    auto out = outputs.find((*i)->string.s);
+    auto out = outputs.find(i->string.s);
     if (out == outputs.end()) {
       throw errMsg;
     }
@@ -190,7 +190,7 @@ bool DrvInfo::checkMeta(Value& v) {
   state->forceValue(v);
   if (v.isList()) {
     for (unsigned int n = 0; n < v.listSize(); ++n) {
-      if (!checkMeta(*v.listElems()[n])) {
+      if (!checkMeta(*(*v.list)[n])) {
         return false;
       }
     }
@@ -418,10 +418,10 @@ static void getDerivations(EvalState& state, Value& vIn,
     for (unsigned int n = 0; n < v.listSize(); ++n) {
       std::string pathPrefix2 =
           addToPath(pathPrefix, (format("%1%") % n).str());
-      if (getDerivation(state, *v.listElems()[n], pathPrefix2, drvs, done,
+      if (getDerivation(state, *(*v.list)[n], pathPrefix2, drvs, done,
                         ignoreAssertionFailures)) {
-        getDerivations(state, *v.listElems()[n], pathPrefix2, autoArgs, drvs,
-                       done, ignoreAssertionFailures);
+        getDerivations(state, *(*v.list)[n], pathPrefix2, autoArgs, drvs, done,
+                       ignoreAssertionFailures);
       }
     }
   }
diff --git a/third_party/nix/src/libexpr/json-to-value.cc b/third_party/nix/src/libexpr/json-to-value.cc
index 4411b411f2..5f8352dde6 100644
--- a/third_party/nix/src/libexpr/json-to-value.cc
+++ b/third_party/nix/src/libexpr/json-to-value.cc
@@ -63,7 +63,7 @@ static void parseJSON(EvalState& state, const char*& s, Value& v) {
 
   if (*s == '[') {
     s++;
-    ValueVector values;
+    NixList values;
     values.reserve(128);
     skipWhitespace(s);
     while (true) {
@@ -85,7 +85,7 @@ static void parseJSON(EvalState& state, const char*& s, Value& v) {
     s++;
     state.mkList(v, values.size());
     for (size_t n = 0; n < values.size(); ++n) {
-      v.listElems()[n] = values[n];
+      (*v.list)[n] = values[n];
     }
   }
 
diff --git a/third_party/nix/src/libexpr/primops.cc b/third_party/nix/src/libexpr/primops.cc
index 6b3eaa4c08..9cda2a1472 100644
--- a/third_party/nix/src/libexpr/primops.cc
+++ b/third_party/nix/src/libexpr/primops.cc
@@ -127,9 +127,10 @@ static void prim_scopedImport(EvalState& state, const Pos& pos, Value** args,
     for (const auto& o : drv.outputs) {
       v2 = state.allocAttr(w, state.symbols.Create(o.first));
       mkString(*v2, o.second.path, {"!" + o.first + "!" + path});
-      outputsVal->listElems()[outputs_index] = state.allocValue();
-      mkString(*(outputsVal->listElems()[outputs_index++]), o.first);
+      (*outputsVal->list)[outputs_index] = state.allocValue();
+      mkString(*((*outputsVal->list)[outputs_index++]), o.first);
     }
+
     Value fun;
     state.evalFile(
         settings.nixDataDir + "/nix/corepkgs/imported-drv-to-derivation.nix",
@@ -231,9 +232,7 @@ static void prim_typeOf(EvalState& state, const Pos& pos, Value** args,
     case tAttrs:
       t = "set";
       break;
-    case tList1:
-    case tList2:
-    case tListN:
+    case tList:
       t = "list";
       break;
     case tLambda:
@@ -360,8 +359,8 @@ static void prim_genericClosure(EvalState& state, const Pos& pos, Value** args,
   state.forceList(*startSet->second.value, pos);
 
   ValueList workSet;
-  for (unsigned int n = 0; n < startSet->second.value->listSize(); ++n) {
-    workSet.push_back(startSet->second.value->listElems()[n]);
+  for (Value* elem : *startSet->second.value->list) {
+    workSet.push_back(elem);
   }
 
   /* Get the operator. */
@@ -404,8 +403,8 @@ static void prim_genericClosure(EvalState& state, const Pos& pos, Value** args,
 
     /* Add the values returned by the operator to the work set. */
     for (unsigned int n = 0; n < call.listSize(); ++n) {
-      state.forceValue(*call.listElems()[n]);
-      workSet.push_back(call.listElems()[n]);
+      state.forceValue(*(*call.list)[n]);
+      workSet.push_back((*call.list)[n]);
     }
   }
 
@@ -413,7 +412,7 @@ static void prim_genericClosure(EvalState& state, const Pos& pos, Value** args,
   state.mkList(v, res.size());
   unsigned int n = 0;
   for (auto& i : res) {
-    v.listElems()[n++] = i;
+    (*v.list)[n++] = i;
   }
 }
 
@@ -620,7 +619,7 @@ static void prim_derivationStrict(EvalState& state, const Pos& pos,
         state.forceList(*i->value, pos);
         for (unsigned int n = 0; n < i->value->listSize(); ++n) {
           std::string s = state.coerceToString(
-              posDrvName, *i->value->listElems()[n], context, true);
+              posDrvName, *(*i->value->list)[n], context, true);
           drv.args.push_back(s);
         }
       }
@@ -651,8 +650,8 @@ static void prim_derivationStrict(EvalState& state, const Pos& pos,
             state.forceList(*i->value, posDrvName);
             Strings ss;
             for (unsigned int n = 0; n < i->value->listSize(); ++n) {
-              ss.emplace_back(state.forceStringNoCtx(*i->value->listElems()[n],
-                                                     posDrvName));
+              ss.emplace_back(
+                  state.forceStringNoCtx(*(*i->value->list)[n], posDrvName));
             }
             handleOutputs(ss);
           }
@@ -942,7 +941,7 @@ static void prim_findFile(EvalState& state, const Pos& pos, Value** args,
   SearchPath searchPath;
 
   for (unsigned int n = 0; n < args[0]->listSize(); ++n) {
-    Value& v2(*args[0]->listElems()[n]);
+    Value& v2(*(*args[0]->list)[n]);
     state.forceAttrs(v2, pos);
 
     std::string prefix;
@@ -1225,7 +1224,7 @@ static void prim_attrNames(EvalState& state, const Pos& pos, Value** args,
 
   unsigned int n = 0;
   for (auto& [key, value] : *args[0]->attrs) {
-    mkString(*(v.listElems()[n++] = state.allocValue()), key);
+    mkString(*((*v.list)[n++] = state.allocValue()), key);
   }
 }
 
@@ -1239,7 +1238,7 @@ static void prim_attrValues(EvalState& state, const Pos& pos, Value** input,
 
   unsigned int n = 0;
   for (auto& [key, value] : *input[0]->attrs) {
-    output.listElems()[n++] = value.value;
+    (*output.list)[n++] = value.value;
   }
 }
 
@@ -1297,8 +1296,8 @@ static void prim_removeAttrs(EvalState& state, const Pos& pos, Value** args,
   /* Get the attribute names to be removed. */
   std::set<Symbol> names;
   for (unsigned int i = 0; i < args[1]->listSize(); ++i) {
-    state.forceStringNoCtx(*args[1]->listElems()[i], pos);
-    names.insert(state.symbols.Create(args[1]->listElems()[i]->string.s));
+    state.forceStringNoCtx(*(*args[1]->list)[i], pos);
+    names.insert(state.symbols.Create((*args[1]->list)[i]->string.s));
   }
 
   /* Copy all attributes not in that set.  Note that we don't need
@@ -1326,7 +1325,7 @@ static void prim_listToAttrs(EvalState& state, const Pos& pos, Value** args,
   std::set<Symbol> seen;
 
   for (unsigned int i = 0; i < args[0]->listSize(); ++i) {
-    Value& v2(*args[0]->listElems()[i]);
+    Value& v2(*(*args[0]->list)[i]);
     state.forceAttrs(v2, pos);
 
     Bindings::iterator j = v2.attrs->find(state.sName);
@@ -1391,7 +1390,7 @@ static void prim_catAttrs(EvalState& state, const Pos& pos, Value** args,
   unsigned int found = 0;
 
   for (unsigned int n = 0; n < args[1]->listSize(); ++n) {
-    Value& v2(*args[1]->listElems()[n]);
+    Value& v2(*(*args[1]->list)[n]);
     state.forceAttrs(v2, pos);
     Bindings::iterator i = v2.attrs->find(attrName);
     if (i != v2.attrs->end()) {
@@ -1401,7 +1400,7 @@ static void prim_catAttrs(EvalState& state, const Pos& pos, Value** args,
 
   state.mkList(v, found);
   for (unsigned int n = 0; n < found; ++n) {
-    v.listElems()[n] = res[n];
+    (*v.list)[n] = res[n];
   }
 }
 
@@ -1472,8 +1471,8 @@ static void elemAt(EvalState& state, const Pos& pos, Value& list, int n,
   if (n < 0 || (unsigned int)n >= list.listSize()) {
     throw Error(format("list index %1% is out of bounds, at %2%") % n % pos);
   }
-  state.forceValue(*list.listElems()[n]);
-  v = *list.listElems()[n];
+  state.forceValue(*(*list.list)[n]);
+  v = *(*list.list)[n];
 }
 
 /* Return the n-1'th element of a list. */
@@ -1499,7 +1498,7 @@ static void prim_tail(EvalState& state, const Pos& pos, Value** args,
   }
   state.mkList(v, args[0]->listSize() - 1);
   for (unsigned int n = 0; n < v.listSize(); ++n) {
-    v.listElems()[n] = args[0]->listElems()[n + 1];
+    (*v.list)[n] = (*args[0]->list)[n + 1];
   }
 }
 
@@ -1510,8 +1509,7 @@ static void prim_map(EvalState& state, const Pos& pos, Value** args, Value& v) {
   state.mkList(v, args[1]->listSize());
 
   for (unsigned int n = 0; n < v.listSize(); ++n) {
-    mkApp(*(v.listElems()[n] = state.allocValue()), *args[0],
-          *args[1]->listElems()[n]);
+    mkApp(*((*v.list)[n] = state.allocValue()), *args[0], *(*args[1]->list)[n]);
   }
 }
 
@@ -1530,9 +1528,9 @@ static void prim_filter(EvalState& state, const Pos& pos, Value** args,
   bool same = true;
   for (unsigned int n = 0; n < args[1]->listSize(); ++n) {
     Value res;
-    state.callFunction(*args[0], *args[1]->listElems()[n], res, noPos);
+    state.callFunction(*args[0], *(*args[1]->list)[n], res, noPos);
     if (state.forceBool(res, pos)) {
-      vs[k++] = args[1]->listElems()[n];
+      vs[k++] = (*args[1]->list)[n];
     } else {
       same = false;
     }
@@ -1543,7 +1541,7 @@ static void prim_filter(EvalState& state, const Pos& pos, Value** args,
   } else {
     state.mkList(v, k);
     for (unsigned int n = 0; n < k; ++n) {
-      v.listElems()[n] = vs[n];
+      (*v.list)[n] = vs[n];
     }
   }
 }
@@ -1554,7 +1552,7 @@ static void prim_elem(EvalState& state, const Pos& pos, Value** args,
   bool res = false;
   state.forceList(*args[1], pos);
   for (unsigned int n = 0; n < args[1]->listSize(); ++n) {
-    if (state.eqValues(*args[0], *args[1]->listElems()[n])) {
+    if (state.eqValues(*args[0], *(*args[1]->list)[n])) {
       res = true;
       break;
     }
@@ -1566,7 +1564,7 @@ static void prim_elem(EvalState& state, const Pos& pos, Value** args,
 static void prim_concatLists(EvalState& state, const Pos& pos, Value** args,
                              Value& v) {
   state.forceList(*args[0], pos);
-  state.concatLists(v, args[0]->listSize(), args[0]->listElems(), pos);
+  state.concatLists(v, *args[0]->list, pos);
 }
 
 /* Return the length of a list.  This is an O(1) time operation. */
@@ -1590,7 +1588,7 @@ static void prim_foldlStrict(EvalState& state, const Pos& pos, Value** args,
       Value vTmp;
       state.callFunction(*args[0], *vCur, vTmp, pos);
       vCur = n == args[2]->listSize() - 1 ? &v : state.allocValue();
-      state.callFunction(vTmp, *args[2]->listElems()[n], *vCur, pos);
+      state.callFunction(vTmp, *(*args[2]->list)[n], *vCur, pos);
     }
     state.forceValue(v);
   } else {
@@ -1606,7 +1604,7 @@ static void anyOrAll(bool any, EvalState& state, const Pos& pos, Value** args,
 
   Value vTmp;
   for (unsigned int n = 0; n < args[1]->listSize(); ++n) {
-    state.callFunction(*args[0], *args[1]->listElems()[n], vTmp, pos);
+    state.callFunction(*args[0], *(*args[1]->list)[n], vTmp, pos);
     bool res = state.forceBool(vTmp, pos);
     if (res == any) {
       mkBool(v, any);
@@ -1639,7 +1637,7 @@ static void prim_genList(EvalState& state, const Pos& pos, Value** args,
   for (unsigned int n = 0; n < (unsigned int)len; ++n) {
     Value* arg = state.allocValue();
     mkInt(*arg, n);
-    mkApp(*(v.listElems()[n] = state.allocValue()), *args[0], *arg);
+    mkApp(*((*v.list)[n] = state.allocValue()), *args[0], *arg);
   }
 }
 
@@ -1651,12 +1649,11 @@ static void prim_sort(EvalState& state, const Pos& pos, Value** args,
   state.forceFunction(*args[0], pos);
   state.forceList(*args[1], pos);
 
-  auto len = args[1]->listSize();
-  state.mkList(v, len);
-  for (unsigned int n = 0; n < len; ++n) {
-    state.forceValue(*args[1]->listElems()[n]);
-    v.listElems()[n] = args[1]->listElems()[n];
-  }
+  // Copy of the input list which can be sorted in place.
+  auto outlist = new (GC) NixList(*args[1]->list);
+
+  std::for_each(outlist->begin(), outlist->end(),
+                [&](Value* val) { state.forceValue(*val); });
 
   auto comparator = [&](Value* a, Value* b) {
     /* Optimization: if the comparator is lessThan, bypass
@@ -1675,7 +1672,7 @@ static void prim_sort(EvalState& state, const Pos& pos, Value** args,
   /* FIXME: std::sort can segfault if the comparator is not a strict
      weak ordering. What to do? std::stable_sort() seems more
      resilient, but no guarantees... */
-  std::stable_sort(v.listElems(), v.listElems() + len, comparator);
+  std::stable_sort(v.list->begin(), v.list->end(), comparator);
 }
 
 static void prim_partition(EvalState& state, const Pos& pos, Value** args,
@@ -1685,36 +1682,28 @@ static void prim_partition(EvalState& state, const Pos& pos, Value** args,
 
   auto len = args[1]->listSize();
 
-  ValueVector right;
-  ValueVector wrong;
+  NixList* right = new (GC) NixList();
+  NixList* wrong = new (GC) NixList();
+
+  for (Value* elem : *args[1]->list) {
+    state.forceValue(*elem, pos);
 
-  for (unsigned int n = 0; n < len; ++n) {
-    auto vElem = args[1]->listElems()[n];
-    state.forceValue(*vElem);
     Value res;
-    state.callFunction(*args[0], *vElem, res, pos);
+    state.callFunction(*args[0], *elem, res, pos);
     if (state.forceBool(res, pos)) {
-      right.push_back(vElem);
+      right->push_back(elem);
     } else {
-      wrong.push_back(vElem);
+      wrong->push_back(elem);
     }
   }
 
   state.mkAttrs(v, 2);
 
   Value* vRight = state.allocAttr(v, state.sRight);
-  auto rsize = right.size();
-  state.mkList(*vRight, rsize);
-  if (rsize != 0u) {
-    memcpy(vRight->listElems(), right.data(), sizeof(Value*) * rsize);
-  }
+  state.mkList(*vRight, right);
 
   Value* vWrong = state.allocAttr(v, state.sWrong);
-  auto wsize = wrong.size();
-  state.mkList(*vWrong, wsize);
-  if (wsize != 0u) {
-    memcpy(vWrong->listElems(), wrong.data(), sizeof(Value*) * wsize);
-  }
+  state.mkList(*vWrong, wrong);
 }
 
 /* concatMap = f: list: concatLists (map f list); */
@@ -1723,27 +1712,18 @@ static void prim_concatMap(EvalState& state, const Pos& pos, Value** args,
                            Value& v) {
   state.forceFunction(*args[0], pos);
   state.forceList(*args[1], pos);
-  auto nrLists = args[1]->listSize();
 
-  Value lists[nrLists];
-  size_t len = 0;
+  NixList* outlist = new (GC) NixList;
 
-  for (unsigned int n = 0; n < nrLists; ++n) {
-    Value* vElem = args[1]->listElems()[n];
-    state.callFunction(*args[0], *vElem, lists[n], pos);
-    state.forceList(lists[n], pos);
-    len += lists[n].listSize();
-  }
+  for (Value* elem : *args[1]->list) {
+    auto out = state.allocValue();
+    state.callFunction(*args[0], *elem, *out, pos);
+    state.forceList(*out, pos);
 
-  state.mkList(v, len);
-  auto out = v.listElems();
-  for (unsigned int n = 0, pos = 0; n < nrLists; ++n) {
-    auto l = lists[n].listSize();
-    if (l != 0u) {
-      memcpy(out + pos, lists[n].listElems(), l * sizeof(Value*));
-    }
-    pos += l;
+    outlist->insert(outlist->end(), out->list->begin(), out->list->end());
   }
+
+  state.mkList(v, outlist);
 }
 
 /*************************************************************
@@ -1908,9 +1888,9 @@ static void prim_match(EvalState& state, const Pos& pos, Value** args,
     state.mkList(v, len);
     for (size_t i = 0; i < len; ++i) {
       if (!match[i + 1].matched) {
-        mkNull(*(v.listElems()[i] = state.allocValue()));
+        mkNull(*((*v.list)[i] = state.allocValue()));
       } else {
-        mkString(*(v.listElems()[i] = state.allocValue()),
+        mkString(*((*v.list)[i] = state.allocValue()),
                  match[i + 1].str().c_str());
       }
     }
@@ -1947,7 +1927,7 @@ static void prim_split(EvalState& state, const Pos& pos, Value** args,
     Value* elem;
 
     if (len == 0) {
-      v.listElems()[idx++] = args[1];
+      (*v.list)[idx++] = args[1];
       return;
     }
 
@@ -1956,27 +1936,27 @@ static void prim_split(EvalState& state, const Pos& pos, Value** args,
       std::smatch match = *i;
 
       // Add a string for non-matched characters.
-      elem = v.listElems()[idx++] = state.allocValue();
+      elem = (*v.list)[idx++] = state.allocValue();
       mkString(*elem, match.prefix().str().c_str());
 
       // Add a list for matched substrings.
       const size_t slen = match.size() - 1;
-      elem = v.listElems()[idx++] = state.allocValue();
+      elem = (*v.list)[idx++] = state.allocValue();
 
       // Start at 1, beacause the first match is the whole string.
       state.mkList(*elem, slen);
       for (size_t si = 0; si < slen; ++si) {
         if (!match[si + 1].matched) {
-          mkNull(*(elem->listElems()[si] = state.allocValue()));
+          mkNull(*((*elem->list)[si] = state.allocValue()));
         } else {
-          mkString(*(elem->listElems()[si] = state.allocValue()),
+          mkString(*((*elem->list)[si] = state.allocValue()),
                    match[si + 1].str().c_str());
         }
       }
 
       // Add a string for non-matched suffix characters.
       if (idx == 2 * len) {
-        elem = v.listElems()[idx++] = state.allocValue();
+        elem = (*v.list)[idx++] = state.allocValue();
         mkString(*elem, match.suffix().str().c_str());
       }
     }
@@ -2010,7 +1990,7 @@ static void prim_concatStringSep(EvalState& state, const Pos& pos, Value** args,
       res += sep;
     }
 
-    res += state.coerceToString(pos, *args[1]->listElems()[n], context);
+    res += state.coerceToString(pos, *(*args[1]->list)[n], context);
   }
 
   mkString(v, res, context);
@@ -2029,14 +2009,14 @@ static void prim_replaceStrings(EvalState& state, const Pos& pos, Value** args,
   std::vector<std::string> from;
   from.reserve(args[0]->listSize());
   for (unsigned int n = 0; n < args[0]->listSize(); ++n) {
-    from.push_back(state.forceString(*args[0]->listElems()[n], pos));
+    from.push_back(state.forceString(*(*args[0]->list)[n], pos));
   }
 
   std::vector<std::pair<std::string, PathSet>> to;
   to.reserve(args[1]->listSize());
   for (unsigned int n = 0; n < args[1]->listSize(); ++n) {
     PathSet ctx;
-    auto s = state.forceString(*args[1]->listElems()[n], ctx, pos);
+    auto s = state.forceString(*(*args[1]->list)[n], ctx, pos);
     to.emplace_back(std::move(s), std::move(ctx));
   }
 
@@ -2116,7 +2096,7 @@ static void prim_splitVersion(EvalState& state, const Pos& pos, Value** args,
   state.mkList(v, components.size());
   unsigned int n = 0;
   for (auto& component : components) {
-    auto listElem = v.listElems()[n++] = state.allocValue();
+    auto listElem = (*v.list)[n++] = state.allocValue();
     mkString(*listElem, component);
   }
 }
@@ -2386,7 +2366,7 @@ void EvalState::createBaseEnv() {
   mkList(v, searchPath.size());
   int n = 0;
   for (auto& i : searchPath) {
-    v2 = v.listElems()[n++] = allocValue();
+    v2 = (*v.list)[n++] = allocValue();
     mkAttrs(*v2, 2);
     mkString(*allocAttr(*v2, symbols.Create("path")), i.second);
     mkString(*allocAttr(*v2, symbols.Create("prefix")), i.first);
diff --git a/third_party/nix/src/libexpr/primops/context.cc b/third_party/nix/src/libexpr/primops/context.cc
index 3a39e03eab..841a45c61c 100644
--- a/third_party/nix/src/libexpr/primops/context.cc
+++ b/third_party/nix/src/libexpr/primops/context.cc
@@ -123,7 +123,7 @@ static void prim_getContext(EvalState& state, const Pos& pos, Value** args,
       state.mkList(outputsVal, info.second.outputs.size());
       size_t i = 0;
       for (const auto& output : info.second.outputs) {
-        mkString(*(outputsVal.listElems()[i++] = state.allocValue()), output);
+        mkString(*((*outputsVal.list)[i++] = state.allocValue()), output);
       }
     }
   }
@@ -184,7 +184,7 @@ static void prim_appendContext(EvalState& state, const Pos& pos, Value** args,
             i->name, i->pos);
       }
       for (unsigned int n = 0; n < iter->second.value->listSize(); ++n) {
-        auto name = state.forceStringNoCtx(*iter->second.value->listElems()[n],
+        auto name = state.forceStringNoCtx(*(*iter->second.value->list)[n],
                                            *iter->second.pos);
         context.insert("!" + name + "!" + std::string(i->name));
       }
diff --git a/third_party/nix/src/libexpr/primops/fromTOML.cc b/third_party/nix/src/libexpr/primops/fromTOML.cc
index 66e2e1b409..389ac08067 100644
--- a/third_party/nix/src/libexpr/primops/fromTOML.cc
+++ b/third_party/nix/src/libexpr/primops/fromTOML.cc
@@ -31,7 +31,7 @@ static void prim_fromTOML(EvalState& state, const Pos& pos, Value** args,
           size_t size2 = i2->get().size();
           state.mkList(v2, size2);
           for (size_t j = 0; j < size2; ++j)
-            visit(*(v2.listElems()[j] = state.allocValue()), i2->get()[j]);
+            visit(*((*v2.list)[j] = state.allocValue()), i2->get()[j]);
         } else
           visit(v2, i.second);
       }
@@ -43,7 +43,7 @@ static void prim_fromTOML(EvalState& state, const Pos& pos, Value** args,
       state.mkList(v, size);
 
       for (size_t i = 0; i < size; ++i)
-        visit(*(v.listElems()[i] = state.allocValue()), t2->get()[i]);
+        visit(*((*v.list)[i] = state.allocValue()), t2->get()[i]);
     }
 
     // Handle cases like 'a = [[{ a = true }]]', which IMHO should be
@@ -56,7 +56,7 @@ static void prim_fromTOML(EvalState& state, const Pos& pos, Value** args,
       state.mkList(v, size);
 
       for (size_t j = 0; j < size; ++j)
-        visit(*(v.listElems()[j] = state.allocValue()), t2->get()[j]);
+        visit(*((*v.list)[j] = state.allocValue()), t2->get()[j]);
     }
 
     else if (t->is_value()) {
diff --git a/third_party/nix/src/libexpr/value-to-json.cc b/third_party/nix/src/libexpr/value-to-json.cc
index a51a1cee30..3e5e025a27 100644
--- a/third_party/nix/src/libexpr/value-to-json.cc
+++ b/third_party/nix/src/libexpr/value-to-json.cc
@@ -64,14 +64,11 @@ void printValueAsJSON(EvalState& state, bool strict, Value& v,
       break;
     }
 
-    case tList1:
-    case tList2:
-    case tListN: {
+    case tList: {
       auto list(out.list());
       for (unsigned int n = 0; n < v.listSize(); ++n) {
         auto placeholder(list.placeholder());
-        printValueAsJSON(state, strict, *v.listElems()[n], placeholder,
-                         context);
+        printValueAsJSON(state, strict, *(*v.list)[n], placeholder, context);
       }
       break;
     }
diff --git a/third_party/nix/src/libexpr/value-to-xml.cc b/third_party/nix/src/libexpr/value-to-xml.cc
index ea1a85a897..aba6013f98 100644
--- a/third_party/nix/src/libexpr/value-to-xml.cc
+++ b/third_party/nix/src/libexpr/value-to-xml.cc
@@ -127,13 +127,11 @@ static void printValueAsXML(EvalState& state, bool strict, bool location,
 
       break;
 
-    case tList1:
-    case tList2:
-    case tListN: {
+    case tList: {
       XMLOpenElement _(doc, "list");
       for (unsigned int n = 0; n < v.listSize(); ++n) {
-        printValueAsXML(state, strict, location, *v.listElems()[n], doc,
-                        context, drvsSeen);
+        printValueAsXML(state, strict, location, *(*v.list)[n], doc, context,
+                        drvsSeen);
       }
       break;
     }
diff --git a/third_party/nix/src/libexpr/value.hh b/third_party/nix/src/libexpr/value.hh
index cb1b8796cf..35c5e4d0a0 100644
--- a/third_party/nix/src/libexpr/value.hh
+++ b/third_party/nix/src/libexpr/value.hh
@@ -1,6 +1,10 @@
 #pragma once
 
+#include <tuple>
+#include <vector>
+
 #include <gc/gc_allocator.h>
+#include <gc/gc_cpp.h>
 
 #include "libexpr/symbol-table.hh"
 #include "libutil/types.hh"
@@ -14,9 +18,7 @@ typedef enum {
   tPath,
   tNull,
   tAttrs,
-  tList1,
-  tList2,
-  tListN,
+  tList,
   tThunk,
   tApp,
   tLambda,
@@ -119,11 +121,6 @@ struct NixString {
   const char** context;  // must be in sorted order
 };
 
-struct NixBigList {
-  size_t size;
-  Value** elems;
-};
-
 struct NixThunk {
   Env* env;
   Expr* expr;
@@ -142,7 +139,9 @@ struct NixPrimOpApp {
   Value *left, *right;
 };
 
-struct Value {
+using NixList = std::vector<Value*, traceable_allocator<Value*>>;
+
+struct Value : public gc {
   ValueType type;
   union {  // TODO(tazjin): std::variant
     NixInt integer;
@@ -150,8 +149,7 @@ struct Value {
     NixString string;
     const char* path;
     Bindings* attrs;
-    NixBigList bigList;
-    Value* smallList[2];
+    NixList* list;
     NixThunk thunk;
     NixApp app;  // TODO(tazjin): "app"?
     NixLambda lambda;
@@ -161,21 +159,9 @@ struct Value {
     NixFloat fpoint;
   };
 
-  bool isList() const {
-    return type == tList1 || type == tList2 || type == tListN;
-  }
-
-  Value** listElems() {
-    return type == tList1 || type == tList2 ? smallList : bigList.elems;
-  }
-
-  const Value* const* listElems() const {
-    return type == tList1 || type == tList2 ? smallList : bigList.elems;
-  }
+  bool isList() const { return type == tList; }
 
-  size_t listSize() const {
-    return type == tList1 ? 1 : type == tList2 ? 2 : bigList.size;
-  }
+  size_t listSize() const { return list->size(); }
 };
 
 /* After overwriting an app node, be sure to clear pointers in the
@@ -242,7 +228,6 @@ void mkPath(Value& v, const char* s);
    not included. */
 size_t valueSize(Value& v);
 
-typedef std::vector<Value*, traceable_allocator<Value*>> ValueVector;
 typedef std::map<Symbol, Value*, std::less<Symbol>,
                  traceable_allocator<std::pair<const Symbol, Value*>>>
     ValueMap;
diff --git a/third_party/nix/src/libstore/worker-protocol.hh b/third_party/nix/src/libstore/worker-protocol.hh
index 663b1ff081..e2f40a449d 100644
--- a/third_party/nix/src/libstore/worker-protocol.hh
+++ b/third_party/nix/src/libstore/worker-protocol.hh
@@ -33,8 +33,8 @@ typedef enum {
   wopQuerySubstitutablePathInfo = 21,
   wopQueryDerivationOutputs = 22,
   wopQueryAllValidPaths = 23,
-  wopQueryFailedPaths = 24, // obsolete
-  wopClearFailedPaths = 25, // obsolete
+  wopQueryFailedPaths = 24,  // obsolete
+  wopClearFailedPaths = 25,  // obsolete
   wopQueryPathInfo = 26,
   wopImportPaths = 27,  // obsolete
   wopQueryDerivationOutputNames = 28,
diff --git a/third_party/nix/src/nix-env/nix-env.cc b/third_party/nix/src/nix-env/nix-env.cc
index 10e2e9492e..07bcb54eb6 100644
--- a/third_party/nix/src/nix-env/nix-env.cc
+++ b/third_party/nix/src/nix-env/nix-env.cc
@@ -158,8 +158,7 @@ static void loadSourceExpr(EvalState& state, const Path& path, Value& v) {
      directory). */
   else if (S_ISDIR(st.st_mode)) {
     state.mkAttrs(v, 1024);
-    state.mkList(*state.allocAttr(v, state.symbols.Create("_combineChannels")),
-                 0);
+    state.mkList(*state.allocAttr(v, state.symbols.Create("_combineChannels")));
     StringSet attrs;
     getAllExprs(state, path, attrs, v);
   }
@@ -1199,11 +1198,11 @@ static void opQuery(Globals& globals, Strings opFlags, Strings opArgs) {
                   attrs2["type"] = "strings";
                   XMLOpenElement m(xml, "meta", attrs2);
                   for (unsigned int j = 0; j < v->listSize(); ++j) {
-                    if (v->listElems()[j]->type != tString) {
+                    if ((*v->list)[j]->type != tString) {
                       continue;
                     }
                     XMLAttrs attrs3;
-                    attrs3["value"] = v->listElems()[j]->string.s;
+                    attrs3["value"] = (*v->list)[j]->string.s;
                     xml.writeEmptyElement("string", attrs3);
                   }
                 } else if (v->type == tAttrs) {
diff --git a/third_party/nix/src/nix-env/user-env.cc b/third_party/nix/src/nix-env/user-env.cc
index 8130eafbdf..06329e74f3 100644
--- a/third_party/nix/src/nix-env/user-env.cc
+++ b/third_party/nix/src/nix-env/user-env.cc
@@ -51,29 +51,29 @@ bool createUserEnv(EvalState& state, DrvInfos& elems, const Path& profile,
        as the meta attributes. */
     Path drvPath = keepDerivations ? i.queryDrvPath() : "";
 
-    Value& v(*state.allocValue());
-    manifest.listElems()[n++] = &v;
-    state.mkAttrs(v, 16);
+    Value* v = state.allocValue();
+    (*manifest.list)[n++] = v;
+    state.mkAttrs(*v, 16);
 
-    mkString(*state.allocAttr(v, state.sType), "derivation");
-    mkString(*state.allocAttr(v, state.sName), i.queryName());
+    mkString(*state.allocAttr(*v, state.sType), "derivation");
+    mkString(*state.allocAttr(*v, state.sName), i.queryName());
     auto system = i.querySystem();
     if (!system.empty()) {
-      mkString(*state.allocAttr(v, state.sSystem), system);
+      mkString(*state.allocAttr(*v, state.sSystem), system);
     }
-    mkString(*state.allocAttr(v, state.sOutPath), i.queryOutPath());
+    mkString(*state.allocAttr(*v, state.sOutPath), i.queryOutPath());
     if (!drvPath.empty()) {
-      mkString(*state.allocAttr(v, state.sDrvPath), i.queryDrvPath());
+      mkString(*state.allocAttr(*v, state.sDrvPath), i.queryDrvPath());
     }
 
     // Copy each output meant for installation.
     DrvInfo::Outputs outputs = i.queryOutputs(true);
-    Value& vOutputs = *state.allocAttr(v, state.sOutputs);
+    Value& vOutputs = *state.allocAttr(*v, state.sOutputs);
     state.mkList(vOutputs, outputs.size());
     unsigned int m = 0;
     for (auto& j : outputs) {
-      mkString(*(vOutputs.listElems()[m++] = state.allocValue()), j.first);
-      Value& vOutputs = *state.allocAttr(v, state.symbols.Create(j.first));
+      mkString(*((*vOutputs.list)[m++] = state.allocValue()), j.first);
+      Value& vOutputs = *state.allocAttr(*v, state.symbols.Create(j.first));
       state.mkAttrs(vOutputs, 2);
       mkString(*state.allocAttr(vOutputs, state.sOutPath), j.second);
 
@@ -86,7 +86,7 @@ bool createUserEnv(EvalState& state, DrvInfos& elems, const Path& profile,
     }
 
     // Copy the meta attributes.
-    Value& vMeta = *state.allocAttr(v, state.sMeta);
+    Value& vMeta = *state.allocAttr(*v, state.sMeta);
     state.mkAttrs(vMeta, 16);
     StringSet metaNames = i.queryMetaNames();
     for (auto& j : metaNames) {
diff --git a/third_party/nix/src/nix-prefetch-url/nix-prefetch-url.cc b/third_party/nix/src/nix-prefetch-url/nix-prefetch-url.cc
index a83ac62635..b9de2e826b 100644
--- a/third_party/nix/src/nix-prefetch-url/nix-prefetch-url.cc
+++ b/third_party/nix/src/nix-prefetch-url/nix-prefetch-url.cc
@@ -50,8 +50,7 @@ std::string resolveMirrorUri(EvalState& state, std::string uri) {
     throw Error(format("mirror URI '%1%' did not expand to anything") % uri);
   }
 
-  std::string mirror =
-      state.forceString(*mirrorList->second.value->listElems()[0]);
+  std::string mirror = state.forceString(*(*mirrorList->second.value->list)[0]);
   return mirror + (absl::EndsWith(mirror, "/") ? "" : "/") +
          std::string(s, p + 1);
 }
@@ -137,7 +136,7 @@ static int _main(int argc, char** argv) {
       if (attr->second.value->listSize() < 1) {
         throw Error("'urls' list is empty");
       }
-      uri = state->forceString(*attr->second.value->listElems()[0]);
+      uri = state->forceString(*(*attr->second.value->list)[0]);
 
       /* Extract the hash mode. */
       attr = v.attrs->find(state->symbols.Create("outputHashMode"));
diff --git a/third_party/nix/src/nix/repl.cc b/third_party/nix/src/nix/repl.cc
index 823bb3b88c..b8edfc0e1c 100644
--- a/third_party/nix/src/nix/repl.cc
+++ b/third_party/nix/src/nix/repl.cc
@@ -748,19 +748,17 @@ std::ostream& NixRepl::printValue(std::ostream& str, Value& v,
       break;
     }
 
-    case tList1:
-    case tList2:
-    case tListN:
+    case tList:
       seen.insert(&v);
 
       str << "[ ";
       if (maxDepth > 0) {
         for (unsigned int n = 0; n < v.listSize(); ++n) {
-          if (seen.find(v.listElems()[n]) != seen.end()) {
+          if (seen.find((*v.list)[n]) != seen.end()) {
             str << "«repeated»";
           } else {
             try {
-              printValue(str, *v.listElems()[n], maxDepth - 1, seen);
+              printValue(str, *(*v.list)[n], maxDepth - 1, seen);
             } catch (AssertionError& e) {
               str << ESC_RED "«error: " << e.msg() << "»" ESC_END;
             }