Dependency graph cycle detection seems too eager, finding cycles where there are none

[sil2100]

Description

Still fresh to the tooling, but this is something I encountered when trying to test-rebuild some things against a new glibc. Scenario: in a PR I was updating glibc and wanted to rebuild binutils (and others) against it in a single PR. Without an explicit glibc-dev dependency (only via build-base), the local glibc was not used. After checking the dag graph code, I added an explicit glibc-dev dep to the build environment. This resulted in a cycle being detected and erroring out:

failed to bundle: targets: cycle detected: binutils:2.43.1-r3@local -> glibc:2.40.9000-r0@local, caused by: glibc:2.40.9000-r0@local -> bash:5.2.37-r2@local -> binutils:2.43.1-r3@local

...which feels to me incorrect, caused by the checker being over-eager. binutils has a glibc-dev dependency, which comes from the glibc source, but the only package from glibc which has the bash runtime dependency is posix-libc-utils, which is not installed when glibc-dev is installed. It simply is part of the glibc set of packages. I feel as if this should not be considered a cycle. Runtime dependencies should matter only for the packages that are installed as part of the chain.

Open to discussion.

[jonjohnsonjr]

I need to parse through this more carefully to see if I'm missing an easy place to fix this, but part of the difficulty here is that everything in glibc.yaml gets built as a single unit, so for build ordering we have to consider the main package together with all of its subpackages.

I do think we conflate runtime and build-time dependencies a bit when constructing the graph, but I've had a hard time trying to understand this logic, much less tease it apart :(

Edit: We should probably diagram this a lot so we can figure out what to do.

[xnox]

I do think we conflate runtime and build-time dependencies a bit when constructing the graph

yes that is happening. it seems like a single set of packages and directions gets involved, instead of two.

One doesn't need to order (all runtime deps) + (all build time deps). only only needs to order (build time deps) versus older ones.

Also a fresher stage3 bootstrap archive would help a lot with this.

[jonjohnsonjr]

One doesn't need to order (all runtime deps) + (all build time deps). only only needs to order (build time deps) versus older ones.

This is tricky because if package B has a runtime dependency on package C, and package A has a build-time dependency on package B, then we need to build package C before package B.

[xnox]

One doesn't need to order (all runtime deps) + (all build time deps). only only needs to order (build time deps) versus older ones.

This is tricky because if package B has a runtime dependency on package C, and package A has a build-time dependency on package B, then we need to build package C before package B.

False, and not enforced by anyone anywhere.

You build them in circle until steady state is met and no new packages are getting produced.

The git merge approach, everyone throws it against the wall until it sticks.

It is also not strictly true. Often enough runtime dependencies are innert and are unused. Because we don't separate out binaries, dlopen, exec things.

Yes a library has dependency on dubs at runtime, but when building against it to link against it dbus binary is not needed. And so on.

[jonjohnsonjr]

You build them in circle until steady state is met and no new packages are getting produced.

This sounds fun, I'm not sure how we'd go about implementing this exactly, but I would definitely like to simplify the build order stuff.

[jonjohnsonjr]

wolfi-dev/os#41342 is the kind of thing where if we can do multi-hop ordering then testing changes is much nicer, but because it's basically impossible to do at the global level, it would be nice if there was some way to supply hints here to force an ordering...