News for hackers. Stuff that matters.
Re:The Magic of Dependency Resolution by menaerus on Wednesday July 12, 2023 @03:53AM (#36691577)
Does anyone know how Linux system package managers solve this problem, SAT or something more? It's also more difficult problem because of having to maintain ABI compatibility.
Re:The Magic of Dependency Resolution by PhilipRoman on Wednesday July 12, 2023 @04:15AM (#36691711)
The Arch Way of doing things involves only ever providing a single version of each package.
Re:The Magic of Dependency Resolution by chriswarbo on Wednesday July 12, 2023 @07:23AM (#36692922)
But which version should they provide? The dependency resolution still needs to happen somewhere ;)
Re:The Magic of Dependency Resolution by PhilipRoman on Wednesday July 12, 2023 @07:52AM (#36693209)
The latest one obviously; any issues are left to the user as an exercise
Re:The Magic of Dependency Resolution by menaerus on Wednesday July 12, 2023 @08:33AM (#36693624)
That's quite surprising but I haven't delved into this topic basically never.

Is it true that yum (dnf), apt and zypper took the approach by having SAT solvers under the hood? If so, why does arch take a different route?

Re:The Magic of Dependency Resolution by rcxdude on Wednesday July 12, 2023 @08:49AM (#36693777)
Because it's easier for the developers. Arch's philosophy very much based on reducing the workload for maintainers. So they package things as close to vanilla as possible (and expect the users to make any adjustments, like enabling any services), package only one version, and have a rolling release which doesn't support older versions or even partial upgrades, so maintainers only really have to worry about making things work with the current version. They were one of the first distros to go exclusively systemd for the same reason of it allowed them to ditch their current init scripts and supporting both is a huge burden.
Re:The Magic of Dependency Resolution by menaerus on Wednesday July 12, 2023 @01:14PM (#36698008)
Interesting. If I have a program A and if I run ldd on it, it outputs dep1, dep2, dep3 and dep4. Now I do the same on program B and ldd shows that it depends on dep1 and dep2, the same ones as from program A.

If I want to update both of them, in the context of program A that would be partial update which AFAIU does not support? But in the context of program B that would be a "full" update. I'm not sure I understand what arch is going to do in this case?

Re:The Magic of Dependency Resolution by rcxdude on Wednesday July 12, 2023 @06:12PM (#36702381)
"partial update" in this case means you update some packages without updating all of them (i.e. do 'pacman -Sy' followed by installing or upgrading any individual package). Usually what will happen is pacman will update those packages and any dependencies but not update any other packages will may now have been broken by that update . So if you were to pacman -Sy <program A> in this case then program B would probably be broken, and vice-versa (assuming any of the common deps have updated as well). If you were to update both then they might be fine but something else may break.

https://wiki.archlinux.org/title/System_maintenance#Partial_...

Re:The Magic of Dependency Resolution by assbuttbuttass on Wednesday July 12, 2023 @09:53AM (#36694540)
I do not think yum or apt use a SAT solver. Instead, if they need multiple versions of a package, they just give them different names

https://packages.debian.org/bookworm/guile-2.2

https://packages.debian.org/bookworm/guile-3.0

Re:The Magic of Dependency Resolution by menaerus on Wednesday July 12, 2023 @11:31AM (#36696058)
From https://fedoraproject.org/wiki/Features/DNF#Including_libsol...

> DNF is a fork of Yum 3.4 that uses libsolv via hawkey for a backend. The main goals of the project are:

> using a SAT solver for dependency resolving allowing us to eventually use the same solver in rpm too > ...

Re:The Magic of Dependency Resolution by skummetmaelk on Wednesday July 12, 2023 @08:47AM (#36693760)
Interesting though that Arch users on the whole seem to experience less system problems than for example Ubuntu users.
Re:The Magic of Dependency Resolution by rcxdude on Wednesday July 12, 2023 @08:51AM (#36693802)
a lot of that comes from the expectation that the user gets their hands dirty in actually configuring most packages in the first place. There's relatively little magic in arch. So both there's less stuff to break and when something does break the user usually can figure out the issue more easily (this is also helped by the selection pressure that is implied by the first expectation).
Re:The Magic of Dependency Resolution by davexunit on Wednesday July 12, 2023 @05:47AM (#36692287)
Modern functional package managers like Guix and Nix do not use SAT solvers because they understand that package variants can differ by a lot more than just their version number. The package graph is explicit in those systems and there are no constraints to solve for.
Re:The Magic of Dependency Resolution by di4na on Wednesday July 12, 2023 @06:14AM (#36692470)
Which is a complex way to say that humans do it by hand.
Re:The Magic of Dependency Resolution by chriswarbo on Wednesday July 12, 2023 @07:21AM (#36692903)
Sometimes; but there are also a bunch of "foo2nix" tools which can generate "packages" (individually, or sets of inter-dependent definitions) from other formats[0]. It's basically just generating (parameterised/overridable) "lock files". That's how Nixpkgs can contains massive collections like haskellPackages, pythonPackages, nodePackages, etc. (plus all the various copies with different compilers/interpreters/flags/etc., thanks to the overriding). It can still require some manual tweaking[1], but CI makes that easier, e.g. translate a few thousand definitions; send to CI; mark all those which fail to build as broken.

[0] Actually, they generate functions which return derivations; Nix doesn't have a concept of "package", although the term gets thrown around informally.

[1] Since those other formats are woefully inadequate at representing dependencies; not just the required compilers/interpreters themselves, but especially stuff like third-party C libraries, binaries that are assumed to be in $PATH, etc.

PS: Those "foo2nix" tools don't need to be manually invoked; they can just be another derivation, whose result gets imported (via the import-from-derivation feature). That's how I tend to manage JVM projects (using mvn2nix).

Re:The Magic of Dependency Resolution by rcxdude on Wednesday July 12, 2023 @08:42AM (#36693719)
yes, but they also don't have the constraint that there can only be one version of a given dependency installed. So once you solve the dependencies for one package you have a solution for any combination of packages, unlike with traditional linux package managers.
Re:The Magic of Dependency Resolution by davexunit on Wednesday July 12, 2023 @08:56AM (#36693872)
I get the sense that you think this approach is inferior, but package managers based on version constraint solvers can't begin to approach the level of automation and reproducibility that exists in functional package managers. Lots of interesting stuff is not done by hand but through transformation with functions.
Re:The Magic of Dependency Resolution by papercrane on Wednesday July 12, 2023 @10:02AM (#36694697)
RPM based distributions typically use dnf, which uses the SAT solver library libsolv https://github.com/openSUSE/libsolv.

I'm not 100% sure if this is current, but APT uses (or used) a heuristics search, but it is possible to configure it to use an external solver instead. See https://salsa.debian.org/apt-team/apt/-/blob/main/doc/extern...

Re:The Magic of Dependency Resolution by j16sdiz on Wednesday July 12, 2023 @03:28PM (#36700369)
Debian use a SAT solver for that.