3 ms·

I feel like the write up doesn't really engage with the number one solution used Don't allow the hard ones Dependency managers tend to just block a huge categ

by Guvante 2mo ago

I feel like the write up doesn't really engage with the number one solution used Don't allow the hard ones Dependency managers tend to just block a huge category of situations that effectively eliminate the entire NP hard space Type systems similarly are explicitly cordoned off The trick isn't "do it anyway" beyond you kind of definitionly need to, it is to acknowledge the general problem is "impossible" so either do your best or start eliminating the impossible

stabbles 2mo ago
Another way to look at it is that in practice N is typically bounded by a large constant, making the time complexity effectively O(1). For dependency resolution specifically, the set of possible dependencies is probably in the range 100 - 10000 for all ecosystems, even if the number of available packages in an ecosystem continues to grow.
- satellite2 2mo ago
  10000? Wait until you meet pip and liberal requirements.txt
  - strbean 2mo ago
    And then you encounter packages with `setup.py` that generates a random list of dependencies on each run. You can't know the dependencies without running code.
silasdavis 2mo ago
Don't allow the hard ones makes the problems P doesn't it?
- singpolyma3 2mo ago
  Kind of the point yes
- Bratmon 2mo ago
  Exactly!
ryangibb 2mo ago
> Dependency managers tend to just block a huge category of situations that effectively eliminate the entire NP hard space Can you elaborate on this? Many _try_ to get around this, e.g. Cargo's https://doc.rust-lang.org/cargo/reference/resolver.html#semver-compatibility https://doc.rust-lang.org/cargo/reference/resolver.html#semv..., but it's not quite in P. Nix offloads dependency resolution to *2nix tools. Go's minimum version selection is just a tree walk, but it loses a fair amount of expressivity.
- inigyou 2mo ago
  Presumably the ones where you are expected to have the latest version of everything and make a new package if you break that (python2 → python3) Not sure why more ecosystems don't do this. Sure an update could break dependents, but, like, you already have a big problem if a dependent was keeping you on an old version no matter what. Building a SAT solver into the package manager seems to be a solution in search of a problem.
  - supriyo-biswas 2mo ago
    > Building a SAT solver into the package manager seems to be a solution in search of a problem. I can't tell you which ones off the top of my head, but I'm sure a number of package managers do use constraint solvers to find dependencies matching the constraints.
    - inigyou 2mo ago
      Most of them do and that's why they are complicated and unreliable.
  - ryangibb 2mo ago
    > Presumably the ones where you are expected to have the latest version of everything and make a new package if you break that (python2 → python3) This is essentially Go's MVS. (Can only specify a minimum bound, can't depend across major version bumps). Any others? MVS is more the exception than the rule. > Not sure why more ecosystems don't do this. Sure an update could break dependents, but, like, you already have a big problem if a dependent was keeping you on an old version no matter what. I'll bite :-) You lose a lot of expressivity. Incompatibility is specified from the dependee, despite being a property of the dependency. I can point to instances where this has causes issues; e.g. dependees using unstable APIs. That's exactly why MVS uses the _minimum_ bound, to minimise such breaks. > Building a SAT solver into the package manager seems to be a solution in search of a problem. I agree in that there are better algorithms for error reporting! But NP-hardness is a pretty fundamental property of dependency resolution and removing it moves the pain somewhere else.
bo1024 2mo ago
A variant: > Don't encounter the hard ones For example, with the simplex method for linear programming, we don't do anything about disallowing the hard instances. We just solve the problems as they come in and none of the ones we get asked to solve ever turn out to be hard. (Generalizing, of course.)

by Guvante 2mo ago

stabbles 2mo ago

Another way to look at it is that in practice N is typically bounded by a large constant, making the time complexity effectively O(1). For dependency resolution specifically, the set of possible dependencies is probably in the range 100 - 10000 for all ecosystems, even if the number of available packages in an ecosystem continues to grow.

satellite2 2mo ago
10000? Wait until you meet pip and liberal requirements.txt
- strbean 2mo ago
  And then you encounter packages with `setup.py` that generates a random list of dependencies on each run. You can't know the dependencies without running code.

silasdavis 2mo ago

Don't allow the hard ones makes the problems P doesn't it?

singpolyma3 2mo ago
Kind of the point yes
Bratmon 2mo ago
Exactly!

ryangibb 2mo ago

> Dependency managers tend to just block a huge category of situations that effectively eliminate the entire NP hard space Can you elaborate on this? Many _try_ to get around this, e.g. Cargo's https://doc.rust-lang.org/cargo/reference/resolver.html#semver-compatibility https://doc.rust-lang.org/cargo/reference/resolver.html#semv..., but it's not quite in P. Nix offloads dependency resolution to *2nix tools. Go's minimum version selection is just a tree walk, but it loses a fair amount of expressivity.

inigyou 2mo ago
Presumably the ones where you are expected to have the latest version of everything and make a new package if you break that (python2 → python3) Not sure why more ecosystems don't do this. Sure an update could break dependents, but, like, you already have a big problem if a dependent was keeping you on an old version no matter what. Building a SAT solver into the package manager seems to be a solution in search of a problem.
- supriyo-biswas 2mo ago
  > Building a SAT solver into the package manager seems to be a solution in search of a problem. I can't tell you which ones off the top of my head, but I'm sure a number of package managers do use constraint solvers to find dependencies matching the constraints.
  - inigyou 2mo ago
    Most of them do and that's why they are complicated and unreliable.
- ryangibb 2mo ago
  > Presumably the ones where you are expected to have the latest version of everything and make a new package if you break that (python2 → python3) This is essentially Go's MVS. (Can only specify a minimum bound, can't depend across major version bumps). Any others? MVS is more the exception than the rule. > Not sure why more ecosystems don't do this. Sure an update could break dependents, but, like, you already have a big problem if a dependent was keeping you on an old version no matter what. I'll bite :-) You lose a lot of expressivity. Incompatibility is specified from the dependee, despite being a property of the dependency. I can point to instances where this has causes issues; e.g. dependees using unstable APIs. That's exactly why MVS uses the _minimum_ bound, to minimise such breaks. > Building a SAT solver into the package manager seems to be a solution in search of a problem. I agree in that there are better algorithms for error reporting! But NP-hardness is a pretty fundamental property of dependency resolution and removing it moves the pain somewhere else.

bo1024 2mo ago

A variant: > Don't encounter the hard ones For example, with the simplex method for linear programming, we don't do anything about disallowing the hard instances. We just solve the problems as they come in and none of the ones we get asked to solve ever turn out to be hard. (Generalizing, of course.)