Nix has a different approach to the problem, with its own set of benefits and drawbacks: packages do not specify version ranges of their dependencies at all; instead they reference them via variables (most commonly -- more generally they can be any arbitrary expression). For example if I'm writing a python package which depends on flask, I might list `flask` as a dependency of my package, or perhaps `flask11` or something.
Whatever that variable resolves to is the thing which will be built (and is itself defined in a similar way), so "version resolution" is replaced with a pure computation, the evaluation of an expression.
This approach offers a great deal of advantages, including very fast (roughly linear) calculation of what to build, full determinism in what gets built, and the ability to specify any arbitrary nix expression as a dependency, say some C library or a command-line tool, rather than being limited just to specifying packages written for your particular language.
However, of course, it does come with some drawbacks. Among them is the requirement that you often can't simply use nix out-of-the-box to build your code; depending on how developed the nix ecosystem is for a particular language, you might have to figure out for language X how packages are built, tested, installed, and linked together, and write the appropriate abstractions in nix. It also means that you won't automatically pick up later versions of a dependency when you (re)build it, which means you might miss out on updates. However, this latter drawback is arguably a benefit, because by the same token you won't accidentally pull in regressions due to an update in a dependency.
I don't understand this. You're saying that the way the dependencies are written down (with code, not declarations) changes the NP-completeness characteristics of dependency resolution.
I strongly doubt that, just like a search in an unindexed database table is O(N) no matter whether you write it as an SQL query or a for loop.
What assumptions about dependencies does Nix make / weaken that makes resolution linear-time? Any of those 4 Russ Cox lists? Or did Nix come up with some genius insight that shows that there's more than 4 core assumptions in the NP Completeness proof and the 5th one is the one that can be safely dropped?
The "fifth" or perhaps "zeroth" assumption is that the versions of all the dependencies must be resolved by a single system. If the developer does half the work by e.g., defining explicitly what flask is, then the remaining part of the system won't have to be NP complete any more.
I think that's what the parent post means by "won't automatically pick up later versions of a dependency". Since it isn't doing full dependency resolution, it doesn't need to solve the whole problem, but also doesn't give all the benefits.
Even though the developer does half the work, the system of 'Nix-using developer + Nix' is still constrained by NP-completeness, so in practice the two combined will not be able to solve the 'dependency resolution problem' in its full generality without a potentially exponential search.
So the real question is, which assumption does the package of 'Nix-using developer + Nix' give up?
As far as I can tell Nix doesn't do dependency resolution at all [1]. Hard linking every dependency is a solution but is undecireable for most systems. I don't want to specify versions for sub-dependencies so I want them to be automatic and we have the NP-problem again. It might be a smaller set of possibilities if most versions are pinned but it's still NP.
[1]: https://medium.com/@charlesstrahan/as-a-nix-nixpkgs-nixos-co...
If by "dependency resolution" you mean solving the SAT-equivalent constraint problem the article talks about, then yes, Nix does not do that.
But, it does solve the simpler problem of installing a package along with the all of its transitive dependencies. Nix packages specify the exact version of each package it depends on, so you never have to recursively specify sub-dependencies. Installation is just a matter of walking an acyclic graph. It's not NP complete.
Actually, his 4th assumption is somewhat broken. A package manager that does automatic upgrades can choose to upgrade all affected packages as a some sort of transaction always keeping a single version and all dependencies resolved without an NP problem.
I would have figured that a bigger strength of Nix in all this is that it does not have assumption 4. With Nix you can have any number of variants of a dependency installed, and each package will find the one it needs.
> I am personally very interested in the idea of allowing packages to mark their dependencies as either "shared" or "internal". We could then disallow shared dependencies from duplicating, but allow internal dependencies to duplicate freely.
CMake has this feature. You can mark dependencies as either public, private or interface. With public meaning that sub dependencies can be reached through public interfaces and private that they just stay inside the program and can be replaced while still maintaining full backwards compatibility with your public interface.
At some point we will do a more in depth write-up about this, but I think we have a very unique take on this at RunKit as we've effectively installed every version of every package. It's actually more interesting than that, we've installed every reasonable combinatorial dependency result of every version of every package on npm.
Long story short, I think there was tremendous insight in npm 2's original model of having every dependency duplicated. Beyond allowing neat things like diffing two versions of the same package (https://runkit.com/tolmasky/api-diff-example-4 ), I think it most accurately portrays the meaning of a package/version.
The fundamental problem with trying to "unify" all the dependencies a program will need, is that it almost guarantees that code will be running in an untested state. Package A was written when Dependency 1 was at version 1.0.0. By assigning it the semver range 1.x.x (instead of the strict 1.0.0 dependency), that means that at some later point it will run against code its never seen or was tested against before. Sure, semver ranges are supposed to protect against this having a "meaningful" effect, but this simply kicks the can down the responsibility chain, changing the error to "human error" as if it makes a difference. For example, let's say at the time of publishing Dependency 1 had a bug that Package A accounted for. According to semver, a fix for this bug would qualify as a 1.0.1, but now Package A's workaround may actually break. The fact of the matter is: 1. rarely is code fully tested, 2. humans can't be trusted to properly assign semver, 3. semver doesn't even account for every possible "meaningful" change (I've seen performance changes that had devastating effects despite the "result" being the same). Different code is different code.
Now, you may be saying, what does this have to do with npm, it sounds like what you want is strict versioning -- the problem is that compounding this already tenuous situation with versions that change depending on the combination of dependencies you have in order to maximize deduping makes this problem even worse. Let me give you a security example:
1. Package A relies on Dependency 1, ranged at 1.x.x.
2. Dependency 1 is found to have a security problem, so a 1.0.1 fix is issued.
3. Package A correctly no longer suffers from this problem.
Later, Package B is added, which someone has maliciously, 10 sup-denendencies deep, added a strict dependency to Dependency 1 1.0.0. The deduping algorithm now says:
1. 1.x.x and 1.0.0 are the requirements, I will use 1.0.0.
Now Package A is using an insecure version of Dependency 1. Previously, if every package was given its own dependencies, the issue would be scoped to Package B, instead it now infects everyone that relies on this Dependency. Sure, you can fix this by saying "dedupe after giving every package its highest possible dependency", but now you still suffer from monkey-patching affecting other code. You end up with very difficult to understand results. Sometimes, all the code uses the same package, other times not, seemingly randomly. The problem is that a performance issue is being turned into a functional issue. Package should be black boxes, not things you change the guts of regularly. There exists a tool for sharing dependencies: "peerDependencies". This says "I expect this to be around" vs. "I am including this".
The basic idea here is that you would never say "let's arbitrarily replace functions I've written in my program with approximately the same function in order to be able to be able to share them and reduce program size". This is nuts! Package versions should be considered hashes that only coincidentally have human names. NPM 2 is the closest I've seen anything come to this, a...
I'm a little confused on what you're proposing. Should package A get the update to 1.0.1 or not? If it does get the update then you still have the problem of "Sometimes, all the code uses the same package, other times not, seemingly randomly." If it doesn't get the update then you keep having a security flaw.
There are two things going on here: 1. the desire to allow every package to install its dependencies separately to guarantee deterministic behavior, and 2. not too take up a lot of disk space. The desired result in this SPECIFIC scenario is simple:
1. Package B contains the faulty Dependency 1 1.0.0.
2. Package A contains the correct Dependency 1 1.0.1.
This is the best case scenario in this situation: Package A is not subject to the security problems of Dependency 1 1.0.0. Package B IS of course, but critical parts of your code are not exposed. If these were the only two packages involved, it would be simple. However the problem arrises from having LOTS of packages, and thus wanting to dedupe, which then leads to having to resolve these semver ranges, or being left with the unfortunate indeterministic behavior of sometimes these being distinct installations and sometimes not.
Thus, to achieve the desired result above AND ensure packages are only installed once on disk, you want to dedupe at the FILESYSTEM level. This is how ied behaves (and I encourage everyone to take a look at its implementation, it is very well done). Essentially, every package is installed and contains symlinks to their dependencies, that way it only takes up space on the hard disk once. However, thanks to node's treat-symlinks-as-real-filepaths option, as far as node is concerned these are distinct installations (as if you had done no deduping at all). Now you have the result from above AND the minimum space on disk.
Yes this proposal is for "functional" languages (where libraries provide functions, and records). JavaScript is a good fit here. When you need "identical" objects across different dependencies, the idea is to specify it as such (npm has a notion of a "peerDependency" <-- this is not a black box object but the requirement that this "exist"). Plugins are a good example of this. If you are building a React plugin, you don't want to require your own React (and then hope the build system dedupes it!), instead you state "I can build when React at this version is present". Once you have this explicit requirement, it is much easier to reason about the (few) "shared" objects. Here most users would raise an eyebrow that for some reason the "resolved" React is a very low version for example.
I would not say the main reason for wildcards is to save disk space. It's to allow updates to happen automatically.
> Package A contains the correct Dependency 1 1.0.1.
What happened to "Package A was written when Dependency 1 was at version 1.0.0."?
If someone in the pinned-version universe was able to update package A to include 1.0.1, the equivalent coder in the semver universe should have updated package A to require "<2 >=1.0.1". Semver dependencies should never lag in necessary updates vs. pinned dependencies in a fair comparison, because they can set an exact minimum.
You'd like Nix. It does just this. Each package declares dependencies on specific versions of other packages. That dependency is expressed as a hash of the inputs to the package, not a semver number. This means that multiple versions of a package can be installed at once, but only copy of each version is installed, unlike npm2.
Security patches are handled by automatically generating new packages that use the patch:
1. Package A relies on Dependency 1, version 1.0.0
2. Dependency 1 is found to have a security problem, so 1.0.1 is issued
3. We generate Package A', which depends on A, but replaces Dep 1 with version 1.0.1
4. Eventually a new version of Package A is released, which depends on Dep 1 at 1.0.1, or maybe a later version
If Package B is introduced with a dependency on the insecure Dependecy 1, only Package B is affected.
1. The npm 2 model breaks down for client-side applications where you want to minimize the size. I don't want 5 slightly different versions of left-pad when 1 will do.
2. I think of semver ranges in package.json as expressing what versions the developer believes should work, and npm-shrinkrap.json or yarn.lock as expressing the latest versions that have actually been tested.
I think it's insane to use npm without shrinkwrap (even though it has its own problems). One of the best things about yarn is it generates yarn.lock by default.
I suppose this view is problematic in the context of RunKit which doesn't have any sort of lock file, and would be challenging to implement UX-wise.
3. Packages with known security issues should be marked as deprecated, which will cause a warning to be printed every time it's installed.
Malicious packages can do a lot worse things than forcing another package's dependency to a specific version, though that is a particularly subtle attack.
AFAICT that's not always true. Several scripting languages allow circular dependencies (Node.js, Perl) and so do some popular package managers (with specific workarounds, but the point is that such dependency constellations exist): https://www.debian.org/doc/debian-policy/ch-relationships.ht...
Perhaps the problem needs to be examined differently depending on allowed/existing-in-the-wild circular dependencies.
And you are right. apt-get has "upgrade" and "dist-upgrade" commands for
a long, long time for a reason (the latter allows to upgrade packages in the
presence of dependency cycles and some other cases that would be nasty if left
in the middle of upgrade; obviously, no changes that need dist-upgrade land in
Debian stable).
If you keep dependencies resolved at all times and operate on packages with hardcoded versions of dependencies, as Nix does, you can avoid that NP-problem.
Sadly, I remember people involved in Go packaging discussions being dismissive of Nix's ideas.
You remember incorrectly. Nix, unfortunately, just isn't suitable for non-final dependency resolution, i.e. libraries. And that's an important part of the mandate for language packaging discussions.
33 comments
[ 3.6 ms ] story [ 65.6 ms ] threadThis approach offers a great deal of advantages, including very fast (roughly linear) calculation of what to build, full determinism in what gets built, and the ability to specify any arbitrary nix expression as a dependency, say some C library or a command-line tool, rather than being limited just to specifying packages written for your particular language.
However, of course, it does come with some drawbacks. Among them is the requirement that you often can't simply use nix out-of-the-box to build your code; depending on how developed the nix ecosystem is for a particular language, you might have to figure out for language X how packages are built, tested, installed, and linked together, and write the appropriate abstractions in nix. It also means that you won't automatically pick up later versions of a dependency when you (re)build it, which means you might miss out on updates. However, this latter drawback is arguably a benefit, because by the same token you won't accidentally pull in regressions due to an update in a dependency.
I strongly doubt that, just like a search in an unindexed database table is O(N) no matter whether you write it as an SQL query or a for loop.
What assumptions about dependencies does Nix make / weaken that makes resolution linear-time? Any of those 4 Russ Cox lists? Or did Nix come up with some genius insight that shows that there's more than 4 core assumptions in the NP Completeness proof and the 5th one is the one that can be safely dropped?
The "fifth" or perhaps "zeroth" assumption is that the versions of all the dependencies must be resolved by a single system. If the developer does half the work by e.g., defining explicitly what flask is, then the remaining part of the system won't have to be NP complete any more.
I think that's what the parent post means by "won't automatically pick up later versions of a dependency". Since it isn't doing full dependency resolution, it doesn't need to solve the whole problem, but also doesn't give all the benefits.
So the real question is, which assumption does the package of 'Nix-using developer + Nix' give up?
But, it does solve the simpler problem of installing a package along with the all of its transitive dependencies. Nix packages specify the exact version of each package it depends on, so you never have to recursively specify sub-dependencies. Installation is just a matter of walking an acyclic graph. It's not NP complete.
CMake has this feature. You can mark dependencies as either public, private or interface. With public meaning that sub dependencies can be reached through public interfaces and private that they just stay inside the program and can be replaced while still maintaining full backwards compatibility with your public interface.
Long story short, I think there was tremendous insight in npm 2's original model of having every dependency duplicated. Beyond allowing neat things like diffing two versions of the same package (https://runkit.com/tolmasky/api-diff-example-4 ), I think it most accurately portrays the meaning of a package/version.
The fundamental problem with trying to "unify" all the dependencies a program will need, is that it almost guarantees that code will be running in an untested state. Package A was written when Dependency 1 was at version 1.0.0. By assigning it the semver range 1.x.x (instead of the strict 1.0.0 dependency), that means that at some later point it will run against code its never seen or was tested against before. Sure, semver ranges are supposed to protect against this having a "meaningful" effect, but this simply kicks the can down the responsibility chain, changing the error to "human error" as if it makes a difference. For example, let's say at the time of publishing Dependency 1 had a bug that Package A accounted for. According to semver, a fix for this bug would qualify as a 1.0.1, but now Package A's workaround may actually break. The fact of the matter is: 1. rarely is code fully tested, 2. humans can't be trusted to properly assign semver, 3. semver doesn't even account for every possible "meaningful" change (I've seen performance changes that had devastating effects despite the "result" being the same). Different code is different code.
Now, you may be saying, what does this have to do with npm, it sounds like what you want is strict versioning -- the problem is that compounding this already tenuous situation with versions that change depending on the combination of dependencies you have in order to maximize deduping makes this problem even worse. Let me give you a security example:
1. Package A relies on Dependency 1, ranged at 1.x.x.
2. Dependency 1 is found to have a security problem, so a 1.0.1 fix is issued.
3. Package A correctly no longer suffers from this problem.
Later, Package B is added, which someone has maliciously, 10 sup-denendencies deep, added a strict dependency to Dependency 1 1.0.0. The deduping algorithm now says:
1. 1.x.x and 1.0.0 are the requirements, I will use 1.0.0.
Now Package A is using an insecure version of Dependency 1. Previously, if every package was given its own dependencies, the issue would be scoped to Package B, instead it now infects everyone that relies on this Dependency. Sure, you can fix this by saying "dedupe after giving every package its highest possible dependency", but now you still suffer from monkey-patching affecting other code. You end up with very difficult to understand results. Sometimes, all the code uses the same package, other times not, seemingly randomly. The problem is that a performance issue is being turned into a functional issue. Package should be black boxes, not things you change the guts of regularly. There exists a tool for sharing dependencies: "peerDependencies". This says "I expect this to be around" vs. "I am including this".
The basic idea here is that you would never say "let's arbitrarily replace functions I've written in my program with approximately the same function in order to be able to be able to share them and reduce program size". This is nuts! Package versions should be considered hashes that only coincidentally have human names. NPM 2 is the closest I've seen anything come to this, a...
1. Package B contains the faulty Dependency 1 1.0.0. 2. Package A contains the correct Dependency 1 1.0.1.
This is the best case scenario in this situation: Package A is not subject to the security problems of Dependency 1 1.0.0. Package B IS of course, but critical parts of your code are not exposed. If these were the only two packages involved, it would be simple. However the problem arrises from having LOTS of packages, and thus wanting to dedupe, which then leads to having to resolve these semver ranges, or being left with the unfortunate indeterministic behavior of sometimes these being distinct installations and sometimes not.
Thus, to achieve the desired result above AND ensure packages are only installed once on disk, you want to dedupe at the FILESYSTEM level. This is how ied behaves (and I encourage everyone to take a look at its implementation, it is very well done). Essentially, every package is installed and contains symlinks to their dependencies, that way it only takes up space on the hard disk once. However, thanks to node's treat-symlinks-as-real-filepaths option, as far as node is concerned these are distinct installations (as if you had done no deduping at all). Now you have the result from above AND the minimum space on disk.
It all depends on what sense you provide to the terms: "minor version" and how you expect your software to be built.
> Package A contains the correct Dependency 1 1.0.1.
What happened to "Package A was written when Dependency 1 was at version 1.0.0."?
If someone in the pinned-version universe was able to update package A to include 1.0.1, the equivalent coder in the semver universe should have updated package A to require "<2 >=1.0.1". Semver dependencies should never lag in necessary updates vs. pinned dependencies in a fair comparison, because they can set an exact minimum.
Security patches are handled by automatically generating new packages that use the patch:
1. Package A relies on Dependency 1, version 1.0.0 2. Dependency 1 is found to have a security problem, so 1.0.1 is issued 3. We generate Package A', which depends on A, but replaces Dep 1 with version 1.0.1 4. Eventually a new version of Package A is released, which depends on Dep 1 at 1.0.1, or maybe a later version
If Package B is introduced with a dependency on the insecure Dependecy 1, only Package B is affected.
IED is at least partially inspired by Nix.
1. The npm 2 model breaks down for client-side applications where you want to minimize the size. I don't want 5 slightly different versions of left-pad when 1 will do.
2. I think of semver ranges in package.json as expressing what versions the developer believes should work, and npm-shrinkrap.json or yarn.lock as expressing the latest versions that have actually been tested.
I think it's insane to use npm without shrinkwrap (even though it has its own problems). One of the best things about yarn is it generates yarn.lock by default.
I suppose this view is problematic in the context of RunKit which doesn't have any sort of lock file, and would be challenging to implement UX-wise.
3. Packages with known security issues should be marked as deprecated, which will cause a warning to be printed every time it's installed.
Malicious packages can do a lot worse things than forcing another package's dependency to a specific version, though that is a particularly subtle attack.
However, this is the killer:
"Two different versions of a package cannot be installed simultaneously."
Get rid of that, and your problems disappear.
Which is why my linux server has:
1 gcc-4.8-base:amd64
2 gcc-4.9-base:amd64
3 gcc-5-base:amd64
4 gcc-6-base:amd64
It seems that the problem then might not even have a solution in all cases. So perhaps we should rethink the problem.
If you allow side-by-side versions then the only remaining failure case is a dependency that doesn't exist.
Nothing to rethink there.
AFAICT that's not always true. Several scripting languages allow circular dependencies (Node.js, Perl) and so do some popular package managers (with specific workarounds, but the point is that such dependency constellations exist): https://www.debian.org/doc/debian-policy/ch-relationships.ht...
Perhaps the problem needs to be examined differently depending on allowed/existing-in-the-wild circular dependencies.
> AFAICT that's not always true.
And you are right. apt-get has "upgrade" and "dist-upgrade" commands for a long, long time for a reason (the latter allows to upgrade packages in the presence of dependency cycles and some other cases that would be nasty if left in the middle of upgrade; obviously, no changes that need dist-upgrade land in Debian stable).
https://www.youtube.com/watch?v=v8F8BqSa-XY
Sadly, I remember people involved in Go packaging discussions being dismissive of Nix's ideas.