Anil Madhavapeddy"Package Managers à la Carte, A Formal Model of Dependency Resolution" preprint out today: a new package calculus to describe the cambrian explosion of systems that exist today https://arxiv.org/pdf/2602.18602 lead by @ryan
Raito Bezarius@ryan I find it interesting that Nix is considered to do singular dependencies only, albeit there's the mention of the various frontend to transform into singular dependencies. I wonder if it has been considered that Nix could provide a builtin to perform version resolution in a package set, e.g. it should be possible given a large enough lockfile to do `builtins.resolveVersions pkgs "gcc" "≤ 14, > 9"` — nonetheless, I understand why the focus is on the peculiar approach of Nix-like systems
@avsm @ryan Yes, I absolutely agree
I have been contemplating introducing generic SAT solving primitives in the Nix language to experiment with these ideas, but I'm not convinced that version resolving is a good idea except by doing it like what Golang is doing but it's not permitted by all ecosystems…
@avsm @ryan What is wondered too is whether that should be application ecosystems which should call into Nix FFI to produce .drv files that can be consumed by a more global system formulae, that way, application ecosystems can translate their build steps into the Nix formalism and reuse all the build machinery (remote builds, sandboxing, caching, etc.) while rendering these paths available to the rest of a Nix expression
ryan@raito @avsm Hi Raito, thanks for the questions! A built-in version solver for Nix is something I've thought about before (primarily when an update of a dependency in Nixpkgs breaks something)! And that's something we could model the particular semantics of (e.g. Cargo-style features are expressed as parameterised derivations in the Nix DSL -- would we support this in the built-in dependency resolution?).
@raito @avsm Static packaging DSLs are relatively straightforward to translate (parsing and emitting in §5.1) but Turing-complete languages like Nix would be more challenging.
Re Golang's MVS, you might have already read it but I elaborate on when this isn't possible due to language constraints in §3.3.
@raito @avsm
I'm quite interested in your idea of a Nix FFI! One of my ideas for a crazy hack was to do cross-ecosystem dependency resolution and use Nix to provide the packages with store derivations! I think the Nix deployment model is great, but it lacks the full-fat dependency resolution of other ecosystems, which is why we see all these x2nix tools. Re opam's nix support, it calls into the Nix CLI rather than creating store derivations manually, but it's in the same spirit :-)
I'm quite interested in your idea of a Nix FFI! One of my ideas for a crazy hack was to do cross-ecosystem dependency resolution and use Nix to provide the packages with store derivations! I think the Nix deployment model is great, but it lacks the full-fat dependency resolution of other ecosystems, which is why we see all these x2nix tools. Re opam's nix support, it calls into the Nix CLI rather than creating store derivations manually, but it's in the same spirit :-)
@ryan @avsm On that tangent, I think it's already possible (and already achieved in some NixOS deployments) by using mount namespaces to mount /nix/store and let things live in another physical Nix store (in the root namespace) which lives in the usual Nix store location (in the workload namespace).
See: https://git.afnix.fr/afnix/infra/src/commit/dcd9d041c8a9c885b65d02ec60d3316ebe2dfe39/services/build-nix-daemon/default.nix for an implementation.
@ryan @avsm I think I'm fairly aligned with the goals of your preprint which is to transform the n^2 problem into an O(n) problem by having a core where every application ecosystem can reduce to. Whether Nix is used as an engine to power that core is something that also interest me. Unfortunately, I have been running out of time to play around with this.
When Python launched a PEP to settle on a format to describe system level dependencies, I had hoped something like that would emerge.
@ryan @avsm In the end, for me, it would be interesting to make Nix interpeters (I work on https://lix.systems but what I'm saying is agnostic tbh) more library-like to allow application package managers or even APT to take it with them and perhaps with the package calculus core, it could be possible to compose these layers and bring an interesting solution to the current plague of packaging.