[DCPM] hierarchies

[Neil Williams]

On Sat, 16 Dec 2006 01:10:39 +0000
Simon Waters <simon at technocool.net> wrote:

> Neil Williams wrote:
> >
> >> Can you define what problem you are trying to solve, rather than
> >> what you think you need to do to solve it.
> >
> > A 'system' (which may be not much more than an ISO image or chroot
> > jail) has a (small) set of packages A and needs a (large) set of
> > packages B. Packages are available elsewhere to go from A to B but
> > these are incompatible with A so each package must be rebuilt using
> > only packages already available in set A. Once successfully built,
> > new packages get included into set A so that you incrementally move
> > closer to a full set B. By following the known dependencies of
> > packages within B, identify the sequence that can build all packages
> > in set B starting from set A. i.e. this is Build-Depends, rather than
> > the binary depends.
>
> If the problem is "how to build B" given A, you don't need to solve this
> elaborate problem.

Unfortunately, I will, because B is a moving target.
:-)

The process of building B from A changes the dependency tree and
thereby changes the process itself. This doesn't normally happen in
Debian but the process of cross-building causes changes in the
dependencies of each package. Extra packages can be generated, stages
omitted and whole branches bypassed. e.g. sqlite pre-depends on debconf
in Debian but debconf depends on perl and perl will not actually be
available in set A (emdebian does not class perl as essential due to
it's size). So Emdebian may predefine what debconf would configure and
omit debconf from the dependencies of sqlite, allowing sqlite to be
built at a different stage of the process. sqlite doesn't need perl
itself, it is only used by debconf to configure sqlite.

Therefore, the output of the script needs to say:
"These packages have no missing dependencies or no dependencies at
all: ...." (Build these).
"These packages have no missing dependencies except dependencies that
are unsupported: ...." (Patch these or drop the package and patch
packages that depend on it).
"These packages have no missing dependencies except dependencies that
cross-building should make unnecessary: ...." (Implement alternatives
to replace these, e.g. predefine what debconf would configure.)

It may prove to be impossible to predict whether some of the initial
build list are eventually unnecessary, that's a price that might just
have to be paid. It just means emdebian carrying a few packages that
never get installed. They should be easy enough to identify afterwards.

> Grow the dependency tree from B till it is complete, which is a trivial
> problem to handle with recursion.

It's trivial to get a *list* of total dependencies. It isn't trivial
(to me) to create a dependency tree, it is the hierarchy that is
difficult.

What structures can implement a usable dependency tree, rather than
just a list?

Package
  |
  ---- dependency1
  |        |
  |        ---------- dependency1.1
  |
  ----- dependency2

I'd find this a lot easier in C if only the original data was as easily
accessible as it is through Perl.
:-(

The main problem is that the depth of the tree cannot be predetermined.
Using references to represent each dependency just gets incredibly
messy when trying to locate dependency12.4.2.7. Now try changing
dependency8.3.1.8.4.7 such that it no longer needs dependency13.9.2.6 !

The most useful effects all happen at the bottom end of the tree, from
the perspective of starting the tree with package set B.

I've got code that can compare the dependencies of a package against
the available packages - it includes handling for versioned-depends and
cross-building artifacts - but it cannot provide a *path* to build the
missing dependencies and their dependencies. It just says "foo missing"
when what it needs to say is "baz, bar, foo missing" in build order.

> Terminate the recursion when you hit a
> package which is in A, or one you already included.

If B is "Gnome" or "Gtk", I can't stop recursion at that point, I need
to go back to a different branch. Following one line may only be two
levels but each dependency of B needs to be tracked all the way back to
A.

Recursion stops when the dependency itself has no dependencies (in the
case of A, it generally ends at tzdata).

> Now loop over the list building any unbuilt package in the list that
> already has its dependencies.

Building each package changes the dependency tree because certain
components can be omitted e.g. language bindings, to save size.

> Loop over the list until everything is
> built, or until an iteration over the loop doesn't improve anything (at
> which point you know the problem has no solution).

It is the storage of the "list" that is troubling me - the ability to
remove or add dependencies and then recalculate the tree. e.g. to
replace debconf with dash (which will simply feed the emdebian defaults
to the package instead of allowing configuration) and work out that the
package has no further unmet dependencies.

(dash replaces bash).

> Presumably you can do this second step "virtually" to check a solution
> exists, before doing anything expensive.

Unreliable - this may be necessary but with the proviso that the tree
is regenerated before builds of packages from the next level are
attempted.

--


Neil Williams
=============
http://www.data-freedom.org/
http://www.nosoftwarepatents.com/
http://www.linux.codehelp.co.uk/

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://mail.pm.org/pipermail/devoncornwall-pm/attachments/20061216/2b6a5ed6/attachment-0001.bin