How do DAGs work within package managers
Posted by Farshief@reddit | linux | View on Reddit | 8 comments
I've been reading about package management and dependency resolution recently and am trying to figure out how the various package managers handle this.
I've learned that instead of a dependency tree like I thought of it previously that it's actually more of a topographical landscape represented by Direct Acyclic Graphs.
So my question specifically is do the maintainers of the various package managers like apt, rpm, etc just have a single central DAG that references in a massive repo of packages; or, do they have smaller DAGs for each package that can be referenced to find out its specific dependencies?
sgorf@reddit
As some others have said, cycles are common. So it’s not a DAG.
DFS_0019287@reddit
While it's true the dependency graph can contain cycles, the solver breaks cycles when calculating dependencies. (Obviously it must, or it would run forever...)
Farshief@reddit (OP)
Yeah I'm realizing that it's much more complex than I originally thought. Luckily I found the aptitude user manual that was pretty helpful in explaining some of what I didn't understand.
That said I know every solution will handle things slightly differently so I'm just trying to gather a general overview
nelmaloc@reddit
Here's Debian's
DFS_0019287@reddit
I believe the DAG is built on-the-fly. Each package declares its dependencies, and the DAG is constructed by recursively following the dependency chain.
I also don't know of any central mechanism for ensuring there are no cycles in the dependency graph. I guess if one is discovered, a bug is filed and it gets fixed?
This picture is complicated somewhat by optional dependencies and by packages that have alternate dependencies. For example, something that needs to send email might depend on `sendmail` or `postfix` or `exim` where any one of those packages satisfies the dependency. (In reality, it would probably depend on a virtual `mta` package that has the actual MTA dependencies.)
xtifr@reddit
Simple cycles in dependencies are generally no problem: if A depends on B and B depends on A, then both packages have to be installed or removed together. Which is fine. Where you get into problems is when packages are marked as conflicting--that is, when you're allowed to install one or the other but not both. If A depends on B and C, but B conflicts with C, then you've got a dependency bug which will prevent A from being installed at all.
MutualRaid@reddit
Colloquially termed Dependency Hell. Almost any time I ended up there as a new user I was compiling and packaging bleeding edge software or mixing repositories before I'd learned the dark arts of apt pinning.
jonringer117@reddit
Nix builds the DAG from bootstrapping tools each time. Figuring out the DAG from a checkout of nixpkgs is the same thing as figuring out from the release channel (Assuming same point in time).
Since nix also hashes each node (derivation in nix terminology), it technically makes a Merkel DAG