Recursive Nix

[edolstra]

Nix builders should be able to call Nix to build things. This is essential if we want to use Nix as a "low-level" build tool (i.e. as a Make replacement), since then we need to support derivations that unpack a source distribution containing a Nix expression to do the rest of the build.

[shlevy]

I agree about the end-goal, but I'm not sure I like (or understand) the means to get there. What exactly would it mean for a builder to realize a derivation while realizing a derivation? Will realization now require knowledge of the Nix language instead of just the lower-level derivation language? Doesn't this remove a lot of the security of all inputs being taken into account by the hash?

I think dynamic import statements are a better approach to this issue. They already exist, they require no modifications to how realisation works, and IMO they better preserve the currently straightforward relationship between the contents of the .drv file and the actions nix takes in realising it. The issues with querying are fixable, I think, by only doing instantiation-time realisation when absolutely necessary for the information requested and when the user allows it (by command line flag or nix.conf setting), and otherwise either failing gracefully or filling in dummy information. I also think a case can be made that a query that doesn't take into account all the relevant derivations (as would happen if realizing a derivation could lead to the realization of arbitrary other derivations) is a broken query anyway.

Do you think it would be possible for you to give a list of blockers that would need to be addressed before you'd be OK with dynamic imports in nixpkgs?

[edolstra]

The idea is that a builder could unpack a source tree containing (among other things) some Nix expressions and call "nix-build -A foo" to build them, just as it can call "make" to build a Make-based package. This is entirely pure, but there is one problem: Nix won't know that the store path produced by the outer build has a potential runtime dependency on the output of the inner build. This is because the hash scanner only looks for paths that appeared in the closure of the inputs. It doesn't know that there is a potential dependency on "foo".

The only thing that we need is for the inner Nix to signal the outer Nix that it's building some paths on behalf of the outer build. The outer Nix would then add these paths to the set of hashes to be scanned for. One simple way to do this:

• The outer Nix sets some environment variable $NIX_RECURSIVE_PATHS pointing to some empty writable file (or maybe pipe or socket).
• When the inner Nix sees that $NIX_RECURSIVE_PATHS is set, it writes the paths it has built to the file denoted $NIX_RECURSIVE_PATHS.
• When the outer build finishes, the outer Nix adds the contents of $NIX_RECURSIVE_PATHS to the input closure.

One minor issue is chroot builds, since there the inner Nix doesn't have access to the complete store. This could be fixed by making the Unix domain socket of the Nix worker available in the chroot.

What do you think? Would there be some way to violate purity with this mechanism?

[shlevy]

Will inner nix-instantiates have access to any out-of-store nix expressions (e.g. nixpkgs)? If so, a single .drv could result in wildly different outputs depending on which version of nixpkgs is present. If not, each inner nix expression will have to bootstrap its dependencies from the ground up (leading to huge amounts of duplication of work and outputs), or nixpkgs itself will need to be an input of the top-level derivation, in which case every nixpkgs checkout will require rebuilding every package that uses nix-build in the builder.

Also, this greatly complicates things and makes queries much less useful. The nice subset relationship between build-time dependencies and run-time dependencies is lost. It's possible the above problem can be fixed and purity thereby maintained, but it makes derivations much less declarative: a change in inputs is only reflected in a change in a tarball's hash instead of in an easily machine-traceable chain of dependencies. It will require new checks for cyclic dependencies to avoid a build doing infinite nix-build recursion.

Why is this preferable to fixing how queries handle dynamic imports? Do you disagree that queries will lose a lot of their value anyway if this system were put into place?

[edolstra]

It's preferable because

• It doesn't require that queries perform a build. Doing a build if you do "nix-env -qa" would be really, really bad.
• It's more scalable. If we were to use Nix as a Make replacement, then the dependency graphs involved might be huge. (1000s or 10,000s of nodes for a single package of the size of Firefox.) With my proposed approach, a query operation doesn't see those "inner" dependency graphs at all. So it's a barrier.

Not having a single graph is too bad, but pretty much unavoidable for these reasons.

I don't see why new checks for cyclic dependencies are necessary. A build can always go into an infinite loop.

I haven't really thought about the Nix expressions used by the inner build, but I think the Nixpkgs source tree (or whatever it wants to use) should be passed in as an ordinary dependency. It could be a copy of the outer Nixpkgs tree though (i.e. you pass "nixpkgsSrc = pkgs.path;" as an attribute). That would require a rebuild of the package if the Nixpkgs tree changes, but if it primary does a nix-build to build itself, a rebuild wouldn't take a lot of time.

[shlevy]

Ok. I think the first point can be fixable (and really leave us no worse off than queries in the recursive build scenario) by just filling in dummy information when a nix-env -qa would have required a build, but your second point is harder to overcome. Maybe having some sort of max depth for queries, or making it so they never recurse into dynamic imports even if the derivation is already built? I'm not sure. I guess I'll just build it instead of talking about it so we can actually see what's possible.

WRT cyclic dependencies: Can we be sure nothing insane (beyond an infinite recursion or a single build failure) happens if an inner build tries to use an outer build as one of its dependencies?

Suppose glibc one day uses nix in place of make, and uses nixpkgs' bootstrap to build itself. Won't the entire system have to be rebuilt when nixpkgs changes? Sure, the glibc build itself will be fast, but what about everything else?

[bluescreen303]

I think the inner build should only be able to use its own Nix expressions and anything the outside wants to pass through (known statically). So it should not be able to import < nixpkgs > or whatever.

For projects using make, it's basically the same. Everything they need is provided thought buildInputs and the like.
Of course we can make the nix-inside-nix experience a bit smoother by not passing env-vars, but by generating/exporting some "from-outside.nix" into the build dir, which the inside builder can import.

I can't think of a good usecase for letting the inside sniff around. The barrier @edolstra talks about should hold 2 ways. If a package wants to use nixpkgs, it should just provide an expression for nixpkgs(outside) which sets this up.

What would be the usecase for having the inside nix expression import/depend on stuff in nixpkgs without statically clarifying this on the outside?

[shlevy]

FWIW, after a nice long civil discussion I think I may have convinced @edolstra that the import-from-derivation route might be better in the long run... So recursive nix may not happen.

[bluescreen303]

Can you explain a bit about that route?

[shlevy]

If you import from a path that is based on a derivation (e.g. import "${nixTarballUnpacked}/build.nix"), then nix will build that derivation before doing the import, all during evaluation time. So packages that want to use nix as a low level build tool can just have their nix expressions in the tarball, then you can unpack it and import those expressions (and pass any arguments you want, if it's a function) from nixpkgs.

The problem with this currently is that the derivation will be built even if you're just querying the package. Most 'sane' imports-from-derivation will probably be just download and unpack a tarball, but even then you don't want to download 100 tarballs just to do nix-env -qa '*'. So we need ways to mitigate that problem, and there are a few good (IMO) options that just need implementing (one implemented in a rough form in #52).

[bluescreen303]

Cool, tnx for the info 👍

I'll have a look at #52 then, it sounds like a nice solution indeed

[Davorak]

@shlevy Are there any examples of build scripts that do this currently that I could take a look at?

[lucabrunox]

What about writing the builder in nix itself instead? I propose a "do" syntactic sugar for a possible ">>" sequential operator.
a >> b evaluates a, discards the result, then evaluates to b.
do { a; b } would evaluate to a >> b.
Assignments might seem to have a little different semantics, but it's only lifting. a = foo would evaluate foo and assign to a.

Then a builder:

builder = do {
  exportEnv "PATH" "$PATH:foo";
  cp "$out/file1" "$out/file2";
  res = grep "pat1" (readFile "$out/file") {};
  writeFile "$out/file" (grep "pat2" res { inverse=true });

and so on. Those $x have to be expanded in the builder environment, and must follow the >>. That is: exportEnv "a" "foo" >> $a must evaluate to "foo".

[edolstra]

Monads!

[lucabrunox]

Yes monads. In a dynamic language like nix shouldn't be hard to achieve. I propose myself to implement/design (or help implementing/designing) such stuff. You are against monads? Don't understand much the nature of your comment :-P

[Ericson2314]

Phase separation, such as quoting the import "${some-drv}/build.nix" sub expr like scheme can solve the query problem, and I believe is good model for recursive nix in general. (To continue phases analogy, manual invoking nix in a build script seems like eval, which, while strictly more powerful than multi-phase has all the usual issues). In particular, nondeterminism relating to dynamic dependencies in this light seems like a problem of macro hygiene.

[taktoa]

Introduction

I spent most of my internship this past summer at Awake Security on making Haskell builds incremental via IFD, and came to the conclusion that any solution to the incremental build problem that involves the build system is going to be brittle and is going to involve essentially reimplementing the logic of your build system in Nix. The right way to go is recursive Nix.

My experience with incrementalization via IFD

I went into this project leaning heavily towards IFD as a solution to the incremental builds via Nix problem. I thought that it was a much more elegant solution when compared to recursive Nix.

The approach I had in mind would have been fairly reusable across different build systems as I was using Ninja as an intermediate representation (i.e.: splitting the task into two tools, cabal2ninja and ninja2nix). Unfortunately Ninja turned out to be a bad fit for the problem domain due to the semantics of its depfile feature; Ninja claims to have "perfect dependencies", but its dependency graph is only ever perfect after the project has been built once, which prevents a tool like ninja2nix from working.

In any case, I still think that, if we are dead-set on not using recursive Nix, the ninja2nix approach is the most practical IFD-based path towards a (partially) incrementalized nixpkgs. Yet it turned out to be very hairy even just for Haskell, let alone CMake or other build systems. This is because there is a fundamental problem with using IFD for incremental builds: it necessarily involves computing a completely static representation of the build graph. To get this data, I was only able to come up with three methods:

1. Modify the build system to compute a static build graph.
2. Instrument the build system, run it in some kind of dry-run mode, and try to compute the build graph from the log output. This log could also be computed in other ways, e.g.: by intercepting the glibc execve wrapper via LD_PRELOAD, but the point is that this method involves actually running the build system and recovering the build graph from data produced via instrumentation.
3. Reimplement the build system from whole cloth (e.g.: in Nix).

Method 1 is generally a lot of work, even for relatively well-written build systems like Cabal, and in some cases (GNU Make, CMake, autotools) is basically impossible.

Method 2 is the easiest option to get working (in the worst case, it would end up linearizing the build graph), but seems tricky to get right, as it depends on you being able to figure out all the information that needs to be printed to recover the dependency graph. If the build system changes, it also seems like it could be very easy for bugs to creep in, as the log might stop being consistent with what you had in mind when you wrote the log "parser".

Method 3 is about as hard as Method 1, and has a huge maintenance burden, as you need to keep the semantics of your reimplementation up to date with the actual build system.

Recursive Nix is the right abstraction

All of the brittleness and difficulty above comes from the fact that we have to care about the build system, and build systems are, in general, very complicated. In contrast, compilers tend to be relatively simple, and in most cases caching each compiler invocation is sufficient to get an incremental build (granted, this is not the case for GHC, but that problem seems relatively tractable, and even if we can't solve it we still get caching at the level of Cabal components).

IFD is also slow, unsuitable for Hydra (without changes to the Hydra evaluator), and creates an enormous build graph. In a world where every build system is written in Nix, it might make sense, but if you want any kind of compatibility with less-well-engineered build systems it becomes a really hard problem.

Conclusion

I think a massive amount of developer time and compute power is being thrown down the drain every day because we don't have this feature, and it should probably be priority number 2 after the UI improvement work.

AFAIK there is considerable interest in incremental builds among industrial users of Nix (Awake Security, Takt, IOHK, Obsidian Systems). Everyday users of Nix(OS) would probably also benefit greatly; in fact, it feels like pretty much every time someone mentions a limitation of Nix it boils down to "you can't safely share work between invocations of nix-build".

I won't be at NixCon this year, but I hope there is a healthy discussion about this feature.

cc @edolstra @Gabriel439 @shlevy @domenkozar @ryantrinkle

[Gabriella439]

The way I link to think about this is that a lot of existing build tools have their own approach to caching build products. Recursive Nix lets you transparently modify them to use Nix to cache their intermediate build products instead

Here's a very common example from our own work environment for developing Haskell packages:

• User uses cabal inside of a nix-shell to do project development
• cabal caches built modules underneath dist/ for incremental builds
• Now the user needs to integrate their project in a larger system
• The project now has to be rebuilt from scratch using nix-build

The elegant solution would be for cabal to use Nix to cache incremental build products instead of using dist/. If you do this correctly then when you switch to nix-build no additional work would need to be done because it would just reuse the build products that cabal had created. Some of our projects take almost 30 minutes to build from scratch, so we prefer to minimize these sorts of wasteful complete rebuilds

There are some other benefits of this approach:

For example, this would improve cabal's caching. Currently, when you use cabal, if you:

• compile the project
• make a change
• compile the project
• revert the change

... you get a wasteful build for the final step since cabal doesn't have a mechanism to save the outputs of old builds once they have been overriden by newer builds. If cabal were to use Nix as the cache for built modules then the last step would be a cache hit

This would also allow users within an organization to share their intermediate build products with each other or to download intermediate build products from a shared cache (i.e. Hydra). I wouldn't need to build anything to seed my local cache of built intermediate modules since I can just download it from Hydra

[ElvishJerricco]

@taktoa @Gabriel439 Sorry, I could use some clarification. How does recursive nix enable incremental building? The only way I can think of to do it would be to reduce e.g. a Haskell derivation to one derivation per module, and somehow coax Cabal into doing nix-build on those (changing Cabal to support this would not help with, say, make). That seems roughly identical to what could be accomplished with IFD, so I'm guessing this is not what you had in mind?

[cleverca22]

what if the cc-wrapper was modified, to just run nix-build, and the dynamically generated derivation then ran gcc?

then it would become a pure nixified version of ccache

[taktoa]

@ElvishJerricco Having Recursive Nix means that we only need to worry about building a drop-in replacement for ghc, and the semantics of Cabal are irrelevant (since Cabal will just run the ghc in the current PATH, which will be a script that ultimately runs nix-build). Since ghc --make has its own build graph, you still need to do a bit of IFD-style trickery (though no actual IFD is involved) to get full incrementalism, but this is much easier than making Cabal generate a static build plan.

[stale]

I marked this as stale due to inactivity. → More info

[stale]

I marked this as stale due to inactivity. → More info

[davidak]

@edolstra what is the status?

What are the next steps to fully support this?

[L-as]

@davidak See RFC 92 for a related alternative, though it's going to be reworked a bit and reworded quite a lot.
It's like what Eelco describes here, except that it's restricted such that you can not use nix build etc. inside the sandbox, you can only do nix-instantiate (equivalent to nix eval --raw) to evaluate the derivation, which you can then output, so that you have a derivation that produces a derivation. You can then use the produced derivation as a normal derivation. This largely solves the same issue as described here, but in a slightly different way.

[stale]

I marked this as stale due to inactivity. → More info

[Ericson2314]

We have an unstable experimental feature to track, so this should stay open.

[roberth]

We now also have a label for tracking the feature.

recursive-nix The recursive-nix experimental feature