nix/libstore/misc.cc

   1 #include "misc.hh"
   2 #include "store-api.hh"
   3 #include "local-store.hh"
   4 #include "globals.hh"
   5
   6
   7 namespace nix {
   8
   9
  10 Derivation derivationFromPath(StoreAPI & store, const Path & drvPath)
  11 {
  12     assertStorePath(drvPath);
  13     store.ensurePath(drvPath);
  14     return parseDerivation(readFile(drvPath));
  15 }
  16
  17
  18 void computeFSClosure(StoreAPI & store, const Path & path,
  19     PathSet & paths, bool flipDirection, bool includeOutputs, bool includeDerivers)
  20 {
  21     if (paths.find(path) != paths.end()) return;
  22     paths.insert(path);
  23
  24     PathSet edges;
  25
  26     if (flipDirection) {
  27         store.queryReferrers(path, edges);
  28
  29         if (includeOutputs) {
  30             PathSet derivers = store.queryValidDerivers(path);
  31             foreach (PathSet::iterator, i, derivers)
  32                 edges.insert(*i);
  33         }
  34
  35         if (includeDerivers && isDerivation(path)) {
  36             PathSet outputs = store.queryDerivationOutputs(path);
  37             foreach (PathSet::iterator, i, outputs)
  38                 if (store.isValidPath(*i) && store.queryDeriver(*i) == path)
  39                     edges.insert(*i);
  40         }
  41
  42     } else {
  43         store.queryReferences(path, edges);
  44
  45         if (includeOutputs && isDerivation(path)) {
  46             PathSet outputs = store.queryDerivationOutputs(path);
  47             foreach (PathSet::iterator, i, outputs)
  48                 if (store.isValidPath(*i)) edges.insert(*i);
  49         }
  50
  51         if (includeDerivers) {
  52             Path deriver = store.queryDeriver(path);
  53             if (store.isValidPath(deriver)) edges.insert(deriver);
  54         }
  55     }
  56
  57     foreach (PathSet::iterator, i, edges)
  58         computeFSClosure(store, *i, paths, flipDirection, includeOutputs, includeDerivers);
  59 }
  60
  61
  62 Path findOutput(const Derivation & drv, string id)
  63 {
  64     foreach (DerivationOutputs::const_iterator, i, drv.outputs)
  65         if (i->first == id) return i->second.path;
  66     throw Error(format("derivation has no output `%1%'") % id);
  67 }
  68
  69
  70 void queryMissing(StoreAPI & store, const PathSet & targets,
  71     PathSet & willBuild, PathSet & willSubstitute, PathSet & unknown,
  72     unsigned long long & downloadSize, unsigned long long & narSize)
  73 {
  74     downloadSize = narSize = 0;
  75
  76     PathSet todo(targets.begin(), targets.end()), done;
  77
  78     /* Getting substitute info has high latency when using the binary
  79        cache substituter.  Thus it's essential to do substitute
  80        queries in parallel as much as possible.  To accomplish this
  81        we do the following:
  82
  83        - For all paths still to be processed (‘todo’), we add all
  84          paths for which we need info to the set ‘query’.  For an
  85          unbuilt derivation this is the output paths; otherwise, it's
  86          the path itself.
  87
  88        - We get info about all paths in ‘query’ in parallel.
  89
  90        - We process the results and add new items to ‘todo’ if
  91          necessary.  E.g. if a path is substitutable, then we need to
  92          get info on its references.
  93
  94        - Repeat until ‘todo’ is empty.
  95     */
  96
  97     while (!todo.empty()) {
  98
  99         PathSet query, todoDrv, todoNonDrv;
 100
 101         foreach (PathSet::iterator, i, todo) {
 102             if (done.find(*i) != done.end()) continue;
 103             done.insert(*i);
 104
 105             DrvPathWithOutputs i2 = parseDrvPathWithOutputs(*i);
 106
 107             if (isDerivation(i2.first)) {
 108                 if (!store.isValidPath(i2.first)) {
 109                     // FIXME: we could try to substitute p.
 110                     unknown.insert(*i);
 111                     continue;
 112                 }
 113                 Derivation drv = derivationFromPath(store, i2.first);
 114
 115                 PathSet invalid;
 116                 foreach (DerivationOutputs::iterator, j, drv.outputs)
 117                     if (wantOutput(j->first, i2.second)
 118                         && !store.isValidPath(j->second.path))
 119                         invalid.insert(j->second.path);
 120                 if (invalid.empty()) continue;
 121
 122                 todoDrv.insert(*i);
 123                 if (settings.useSubstitutes && !willBuildLocally(drv))
 124                     query.insert(invalid.begin(), invalid.end());
 125             }
 126
 127             else {
 128                 if (store.isValidPath(*i)) continue;
 129                 query.insert(*i);
 130                 todoNonDrv.insert(*i);
 131             }
 132         }
 133
 134         todo.clear();
 135
 136         SubstitutablePathInfos infos;
 137         store.querySubstitutablePathInfos(query, infos);
 138
 139         foreach (PathSet::iterator, i, todoDrv) {
 140             DrvPathWithOutputs i2 = parseDrvPathWithOutputs(*i);
 141
 142             // FIXME: cache this
 143             Derivation drv = derivationFromPath(store, i2.first);
 144
 145             PathSet outputs;
 146             bool mustBuild = false;
 147             if (settings.useSubstitutes && !willBuildLocally(drv)) {
 148                 foreach (DerivationOutputs::iterator, j, drv.outputs) {
 149                     if (!wantOutput(j->first, i2.second)) continue;
 150                     if (!store.isValidPath(j->second.path)) {
 151                         if (infos.find(j->second.path) == infos.end())
 152                             mustBuild = true;
 153                         else
 154                             outputs.insert(j->second.path);
 155                     }
 156                 }
 157             } else
 158                 mustBuild = true;
 159
 160             if (mustBuild) {
 161                 willBuild.insert(i2.first);
 162                 todo.insert(drv.inputSrcs.begin(), drv.inputSrcs.end());
 163                 foreach (DerivationInputs::iterator, j, drv.inputDrvs)
 164                     todo.insert(makeDrvPathWithOutputs(j->first, j->second));
 165             } else
 166                 todoNonDrv.insert(outputs.begin(), outputs.end());
 167         }
 168
 169         foreach (PathSet::iterator, i, todoNonDrv) {
 170             done.insert(*i);
 171             SubstitutablePathInfos::iterator info = infos.find(*i);
 172             if (info != infos.end()) {
 173                 willSubstitute.insert(*i);
 174                 downloadSize += info->second.downloadSize;
 175                 narSize += info->second.narSize;
 176                 todo.insert(info->second.references.begin(), info->second.references.end());
 177             } else
 178                 unknown.insert(*i);
 179         }
 180     }
 181 }
 182
 183
 184 static void dfsVisit(StoreAPI & store, const PathSet & paths,
 185     const Path & path, PathSet & visited, Paths & sorted,
 186     PathSet & parents)
 187 {
 188     if (parents.find(path) != parents.end())
 189         throw BuildError(format("cycle detected in the references of `%1%'") % path);
 190
 191     if (visited.find(path) != visited.end()) return;
 192     visited.insert(path);
 193     parents.insert(path);
 194
 195     PathSet references;
 196     if (store.isValidPath(path))
 197         store.queryReferences(path, references);
 198
 199     foreach (PathSet::iterator, i, references)
 200         /* Don't traverse into paths that don't exist.  That can
 201            happen due to substitutes for non-existent paths. */
 202         if (*i != path && paths.find(*i) != paths.end())
 203             dfsVisit(store, paths, *i, visited, sorted, parents);
 204
 205     sorted.push_front(path);
 206     parents.erase(path);
 207 }
 208
 209
 210 Paths topoSortPaths(StoreAPI & store, const PathSet & paths)
 211 {
 212     Paths sorted;
 213     PathSet visited, parents;
 214     foreach (PathSet::const_iterator, i, paths)
 215         dfsVisit(store, paths, *i, visited, sorted, parents);
 216     return sorted;
 217 }
 218
 219
 220 }