Re: topological sorting

[Greg Troxel <gdt%lexort.com@localhost>]

tlaronde%polynum.com@localhost writes:

> It seems to me that if a package depends on A, B, C, the building or
> installation tries to build A, then B, then C. It doesn't try to see if
> there are common dependencies to A, B and C and try to build the common dependencies
> first, starting by the "most" common ones? It recurses by package?

It does depth-first traversal, because when it builds A, then first
anything that A depends on needs to be installed.  Either because it is
installed, or else it gets built and installed.

And, it calls "make package-install" or whatever on A, which then
creates a workdir and doesn't do much and then recurses to B.  So
technically it is no entirely doing B first, but very close.

It does not attempt to find any maximally-distant package.  But as I
said all topologogically correct orders are valid and you are perhaps
wanting tie breaking by some more complicated property.

> My problem---some packages are quite complex so this is not criticism: I
> know this is difficult, that there are too many variables and that the
> upstream version is not always optimal; and I'm glad I don't have to
> tackle the problem of building or installing some monsters on my own
> ;-)---so my problem is that more than once, I have been eaten by a build
> that took hours, installing a bunch of intermediary dependencies, to
> finally fail on something, meaning that a bunch of things have been
> added that are useless and tons of bytes have been downloaded that will
> be useless too since there are probably other versions that need to be
> fetched in order for the build to succeed.

In theory, make package anywhere in pkgsrc will succeed.  In practice,
not entirely.  Usually though the way to fix is to fix something, rather
than to decide not to use most of it.

> I'm trying to find a way to fail (if that has to fail) as early as possible
> and with the minimum amount of work done...

That will take defining what you want and writing an optimization
program based on pbulk-scan or pkgin.

> And, alternatively, I want to know what package has installed/required
> TeXlive (!) so this is why I wanted to know if the dependencies graph
> could be obtained by one of the tools (even if I know how to do it by
> scripting).

pkg_info shows depending packages.