(31-05-2020, 02:47 AM)vain Wrote: Isn't building a dependency tree and then doing topological sort enough? (Possibly by simply resolving dependencies recursively?)

Well that's already a bit complex. But the most complex part isn't to "find" the dependencies. It is to keep them up to date and accurate when you maintain your own package infrastructure. Because you need to find a clean way to ensure that you actually listed all required dependency. An eventual solution is to build packs in a chroot where you only install those deps for example.
And then you'll also face the "build VS. runtime" dependency problem…

Really, what's complex with dependency resolution, is to get them right in the first place.

Oh. and there is the cyclic dependencies handling problem too. How do you deal with this:

gcc: require libc, libstdc++, make, gcc
libc: require gcc

It is mostly an issue at build time (though you can find cyclic deps at runtime too…), but you'll encounter this fairly often, especially for the components of your toolchain.