[Fink-devel] More on dependencies...

[Max H. <ma...@qu...>]

Hrm, I never got to finish that second email on the topic I promised 
a long time ago. So I decided to tie up some loose end on the 
incomplete draft I never sent. It doesn't touch a lot of things, but 
better than sending this to the dust bin.

In the meantime, I noticed that there is "pkg-order", a tool that 
orders dependencies, written in Perl. It does a lot of the things we 
need to do, in fact almost everything except for BuildDependends. 
Unfortunately, those are the hardest to deal with. More at the end of 
this email. Another thing it lacks a bit in (AFAICT) is how it deals 
with alternate possibilities to fulfill a dependency...



------------------------


So, in this mail, I will tell you some ideas on how to deal with 
build dependencies (and building packages in general vs. just 
installing them). I also will explain things the core dependency 
engine (minus build time stuff) has to do, and also how we could do 
them (and also discuss the feasibility of using apt's engine for this 
work). As always, comments (positive or negative) are welcome, and 
suggestions for improvements even more.


Build dependencies (and the fact that fink can build packages on the 
fly in the first place) are the major point that makes our life 
harder than it is for apt-get or dpkg. So, following the good old 
KISS principle let us simply ignore it at first, and look at the 
issues we have. Once we know how to solve these, we can start 
worrying about build issues...


Resolving dependencies (or: "Baby, it's all about choices")
======================

So, we ignore build deps (and build conflicts) completely for now. 
Furthermore, we assume package dependencies are sane - no circular 
deps, no "impossible installs" (like foo depends on bar and qux, but 
bar and qux conflict). Of course we should detect these and bail out 
with a sensible error if we encounter them, but that's not what I 
want to write about here.

One should note that apt (and also dpkg, though with less power) 
already has a dependency engine which covers this case, as it deals 
with all the kinds of dependencies fink needs (minus build deps of 
course). Hence it might be a good idea to try to adapt its engine for 
fink (why reinvent the wheel?). Of course we'd have to interface perl 
and c(++) for this. We also would have to figure out how to hook into 
the apt-get code. We'd need to marry it with our code that deals with 
build deps, too (but that's covered in the next section). We also 
need to override apt's way of choosing which package to use to 
fulfill a multiple choice dependency (apt just use the first possible 
combination, it seems, while Fink tries to ask the user for his 
wishes). This all adds up to some complication. So while I still 
think we should at least consider it, it might not be worth the 
effort after all. In any case we can try to look at their sources and 
learn from them (how they solved various problems etc.).

[... here I never finished what I wanted to write.]






Dealing with build time
=======================

Several different approaches are possible... all have their issues 
and advantages

The dumb way
------------
This is mostly how we do it now. But if we combine this with 
pkg-order, it might still be better than the current code...

Roughly, what you do is this: when hooking into pkg-order, when it 
asks us for the deps of package "foo", we check if a .deb is 
available for it. If yes, we return just the deps; if no we return 
the deps merged with the build deps (actually this is a bit more 
complicated for splitoffs, but we already have the code for all this 
anyway).

Pro: this is straight forward to implement (we already do it this way 
afterall).
Con: Is not very flexible; e.g. if  package  "foo" needs "bar" as a 
build dependency, and another pkg  "qux" later conflicts with "bar", 
we can't proceed, rather the user has to manually issues several 
commands (first building "foo", then removing "bar", then installing 
"quy").


The proper way
--------------

Proper would be to (as I mentioned in the past) have a full fledged 
package orderer that is aware of the fact that build dependencies can 
be removed after they have been used. My hope is that it's possible 
to add support for this to pkg-order, maybe one could even get 
support from the pkg-order author(s) for this project. However, I 
consider it a hard piece of work to be done properly.

Also, when in doubt about multiple possible ways to fulfill a 
dependency, it should be possible to either let fink make a good 
(automatic) guess at it, *or* let fink ask the user what he prefers. 
Not sure how hard it would be to implement that atop pkg-order.

Pro: This is very powerful, and flexible, and gives the best user experience
Con: Quite hard to implement in my estimation

[Note: I wanted to go more into detail here, but never finished it]


Chroot jail
-----------

The idea is to build packages as we do it now, with the only 
exception that we first chroot into a custom root directory.  For a 
chroot jail to work (i.e. in order to be able to run program in it), 
all necessary libraries (including system libraries) have to be 
existent inside the jail. This usually means copying these libraries 
(hard links might work, but only if the build dir is on the same 
drive as the system, which is not necessarily true for fink). And of 
course if you want to compile stuff, the header files and tools 
(compiler, linker, ...) are needed, too).

This immediately shows a big limitation: such a jail has to be built, 
which takes time, and disk space (potentially a lot). The advantages, 
though, are:
* the /sw we put into the jail can be custom made: that is, it would 
only contain the minimal dependencies of the package being built, 
thus avoiding hidden dependencies much better
* build dependencies of the pkg are never installed in the real /sw, 
thus avoiding any problems they can cause, dependency wise (like 
conflicting with the build deps of another package)
* detecting files that get installed directly into /sw during build 
is easier (because they will be missing from the real /sw)
* multiple build runs are easily possible (although they would take a 
lot of disk space), even if the builds have conflicting dependencies
* no more problem caused by users running "fink remove FOO" while 
something is building that depends on foo

Essentially, since with this approach build dependency/conflicts only 
have to be resolved in the context of the chroot jail, we can indeed 
completely ignore them for our "normal" dependency engine.

Overall, the chroot approach solves a lot of annoying issues very 
neatly. However, the additional disk space for the chroot jail(s) 
(and the CPU time to set them up) are quite severe limitation. Of 
course modern machines have plenty of disk space and CPU power, but 
e.g. my iBook G3/500 only has 1 GB free on its HD. For my daily fink 
usage that's fine, but if I suddenly need several 100 MBs to setup 
chroot jails, that would be annoying. We might be able to severely 
cut this down if we can use hardlinks when building on the same 
volume as the system is on. This definitely requires research should 
we decide to consider using it :-)

Another tricky thing about the chroot jail approach is to make it 
work efficiently when used "recursively". To understand what I mean, 
consider this: The .deb for pkg "foo" (which we want to install) is 
missing. We already ensured all its dependencies are fulfilled. Now 
"foo" BuildDepends on "bar", for which the .deb is also missing! 
Hence we first have to recurse to get "bar" built (with its own 
chroot jail)... and of course "bar" might depend on more things which 
need to be built first.


Pro: Relatively easy to implement; could be implemented atop 
pkg-order; also allows to detect hidden dependencies
Con: Takes up additional disk space & CPU time; might have unforseen problems



Cheers,

Max