1 files changed, 331 insertions, 0 deletions
diff --git a/third_party/nix/src/libstore/misc.cc b/third_party/nix/src/libstore/misc.cc
new file mode 100644
index 000000000000..44e67ada369c
--- /dev/null
+++ b/third_party/nix/src/libstore/misc.cc
@@ -0,0 +1,331 @@
+#include <glog/logging.h>
+
+#include "libstore/derivations.hh"
+#include "libstore/globals.hh"
+#include "libstore/local-store.hh"
+#include "libstore/parsed-derivations.hh"
+#include "libstore/store-api.hh"
+#include "libutil/thread-pool.hh"
+
+namespace nix {
+
+void Store::computeFSClosure(const PathSet& startPaths, PathSet& paths_,
+                             bool flipDirection, bool includeOutputs,
+                             bool includeDerivers) {
+  struct State {
+    size_t pending;
+    PathSet& paths;
+    std::exception_ptr exc;
+  };
+
+  Sync<State> state_(State{0, paths_, nullptr});
+
+  std::function<void(const Path&)> enqueue;
+
+  std::condition_variable done;
+
+  enqueue = [&](const Path& path) -> void {
+    {
+      auto state(state_.lock());
+      if (state->exc) {
+        return;
+      }
+      if (state->paths.count(path) != 0u) {
+        return;
+      }
+      state->paths.insert(path);
+      state->pending++;
+    }
+
+    queryPathInfo(
+        path,
+        Callback<ref<ValidPathInfo>>(
+            [&, path](std::future<ref<ValidPathInfo>> fut) {
+              // FIXME: calls to isValidPath() should be async
+
+              try {
+                auto info = fut.get();
+
+                if (flipDirection) {
+                  PathSet referrers;
+                  queryReferrers(path, referrers);
+                  for (auto& ref : referrers) {
+                    if (ref != path) {
+                      enqueue(ref);
+                    }
+                  }
+
+                  if (includeOutputs) {
+                    for (auto& i : queryValidDerivers(path)) {
+                      enqueue(i);
+                    }
+                  }
+
+                  if (includeDerivers && isDerivation(path)) {
+                    for (auto& i : queryDerivationOutputs(path)) {
+                      if (isValidPath(i) && queryPathInfo(i)->deriver == path) {
+                        enqueue(i);
+                      }
+                    }
+                  }
+
+                } else {
+                  for (auto& ref : info->references) {
+                    if (ref != path) {
+                      enqueue(ref);
+                    }
+                  }
+
+                  if (includeOutputs && isDerivation(path)) {
+                    for (auto& i : queryDerivationOutputs(path)) {
+                      if (isValidPath(i)) {
+                        enqueue(i);
+                      }
+                    }
+                  }
+
+                  if (includeDerivers && isValidPath(info->deriver)) {
+                    enqueue(info->deriver);
+                  }
+                }
+
+                {
+                  auto state(state_.lock());
+                  assert(state->pending);
+                  if (--state->pending == 0u) {
+                    done.notify_one();
+                  }
+                }
+
+              } catch (...) {
+                auto state(state_.lock());
+                if (!state->exc) {
+                  state->exc = std::current_exception();
+                }
+                assert(state->pending);
+                if (--state->pending == 0u) {
+                  done.notify_one();
+                }
+              };
+            }));
+  };
+
+  for (auto& startPath : startPaths) {
+    enqueue(startPath);
+  }
+
+  {
+    auto state(state_.lock());
+    while (state->pending != 0u) {
+      state.wait(done);
+    }
+    if (state->exc) {
+      std::rethrow_exception(state->exc);
+    }
+  }
+}
+
+void Store::computeFSClosure(const Path& startPath, PathSet& paths_,
+                             bool flipDirection, bool includeOutputs,
+                             bool includeDerivers) {
+  computeFSClosure(PathSet{startPath}, paths_, flipDirection, includeOutputs,
+                   includeDerivers);
+}
+
+void Store::queryMissing(const PathSet& targets, PathSet& willBuild_,
+                         PathSet& willSubstitute_, PathSet& unknown_,
+                         unsigned long long& downloadSize_,
+                         unsigned long long& narSize_) {
+  LOG(INFO) << "querying info about missing paths";
+
+  downloadSize_ = narSize_ = 0;
+
+  ThreadPool pool;
+
+  struct State {
+    PathSet done;
+    PathSet &unknown, &willSubstitute, &willBuild;
+    unsigned long long& downloadSize;
+    unsigned long long& narSize;
+  };
+
+  struct DrvState {
+    size_t left;
+    bool done = false;
+    PathSet outPaths;
+    explicit DrvState(size_t left) : left(left) {}
+  };
+
+  Sync<State> state_(State{PathSet(), unknown_, willSubstitute_, willBuild_,
+                           downloadSize_, narSize_});
+
+  std::function<void(Path)> doPath;
+
+  auto mustBuildDrv = [&](const Path& drvPath, const Derivation& drv) {
+    {
+      auto state(state_.lock());
+      state->willBuild.insert(drvPath);
+    }
+
+    for (auto& i : drv.inputDrvs) {
+      pool.enqueue(
+          std::bind(doPath, makeDrvPathWithOutputs(i.first, i.second)));
+    }
+  };
+
+  auto checkOutput = [&](const Path& drvPath, const ref<Derivation>& drv,
+                         const Path& outPath,
+                         const ref<Sync<DrvState>>& drvState_) {
+    if (drvState_->lock()->done) {
+      return;
+    }
+
+    SubstitutablePathInfos infos;
+    querySubstitutablePathInfos({outPath}, infos);
+
+    if (infos.empty()) {
+      drvState_->lock()->done = true;
+      mustBuildDrv(drvPath, *drv);
+    } else {
+      {
+        auto drvState(drvState_->lock());
+        if (drvState->done) {
+          return;
+        }
+        assert(drvState->left);
+        drvState->left--;
+        drvState->outPaths.insert(outPath);
+        if (drvState->left == 0u) {
+          for (auto& path : drvState->outPaths) {
+            pool.enqueue(std::bind(doPath, path));
+          }
+        }
+      }
+    }
+  };
+
+  doPath = [&](const Path& path) {
+    {
+      auto state(state_.lock());
+      if (state->done.count(path) != 0u) {
+        return;
+      }
+      state->done.insert(path);
+    }
+
+    DrvPathWithOutputs i2 = parseDrvPathWithOutputs(path);
+
+    if (isDerivation(i2.first)) {
+      if (!isValidPath(i2.first)) {
+        // FIXME: we could try to substitute the derivation.
+        auto state(state_.lock());
+        state->unknown.insert(path);
+        return;
+      }
+
+      Derivation drv = derivationFromPath(i2.first);
+      ParsedDerivation parsedDrv(i2.first, drv);
+
+      PathSet invalid;
+      for (auto& j : drv.outputs) {
+        if (wantOutput(j.first, i2.second) && !isValidPath(j.second.path)) {
+          invalid.insert(j.second.path);
+        }
+      }
+      if (invalid.empty()) {
+        return;
+      }
+
+      if (settings.useSubstitutes && parsedDrv.substitutesAllowed()) {
+        auto drvState = make_ref<Sync<DrvState>>(DrvState(invalid.size()));
+        for (auto& output : invalid) {
+          pool.enqueue(std::bind(checkOutput, i2.first,
+                                 make_ref<Derivation>(drv), output, drvState));
+        }
+      } else {
+        mustBuildDrv(i2.first, drv);
+      }
+
+    } else {
+      if (isValidPath(path)) {
+        return;
+      }
+
+      SubstitutablePathInfos infos;
+      querySubstitutablePathInfos({path}, infos);
+
+      if (infos.empty()) {
+        auto state(state_.lock());
+        state->unknown.insert(path);
+        return;
+      }
+
+      auto info = infos.find(path);
+      assert(info != infos.end());
+
+      {
+        auto state(state_.lock());
+        state->willSubstitute.insert(path);
+        state->downloadSize += info->second.downloadSize;
+        state->narSize += info->second.narSize;
+      }
+
+      for (auto& ref : info->second.references) {
+        pool.enqueue(std::bind(doPath, ref));
+      }
+    }
+  };
+
+  for (auto& path : targets) {
+    pool.enqueue(std::bind(doPath, path));
+  }
+
+  pool.process();
+}
+
+Paths Store::topoSortPaths(const PathSet& paths) {
+  Paths sorted;
+  PathSet visited;
+  PathSet parents;
+
+  std::function<void(const Path& path, const Path* parent)> dfsVisit;
+
+  dfsVisit = [&](const Path& path, const Path* parent) {
+    if (parents.find(path) != parents.end()) {
+      throw BuildError(
+          format("cycle detected in the references of '%1%' from '%2%'") %
+          path % *parent);
+    }
+
+    if (visited.find(path) != visited.end()) {
+      return;
+    }
+    visited.insert(path);
+    parents.insert(path);
+
+    PathSet references;
+    try {
+      references = queryPathInfo(path)->references;
+    } catch (InvalidPath&) {
+    }
+
+    for (auto& i : references) {
+      /* Don't traverse into paths that don't exist.  That can
+         happen due to substitutes for non-existent paths. */
+      if (i != path && paths.find(i) != paths.end()) {
+        dfsVisit(i, &path);
+      }
+    }
+
+    sorted.push_front(path);
+    parents.erase(path);
+  };
+
+  for (auto& i : paths) {
+    dfsVisit(i, nullptr);
+  }
+
+  return sorted;
+}
+
+}  // namespace nix