WP2 Overview
Goal One: analysing package repositories
We want to develop a tool to perform sophisticated static analysis on
a special kind of graph that represent a collection of packages together
with their historical evolution (versions/variants/forks, etc.).
This graph should take into account _all kind_ of dependencies:
Build (or source) dependencies: prerequisites for _building/compiling_ a package
Binary dependencies: prerequisites for _installing_ a package
Configuration dependencies: prerequisites for _configuring_ a package
Conflicts: _incompatibilities_ between packages, at different levels (install/configuration)
Replacements: _relations_ between packages that may replace each other's functionality (ex: senmail vs exim)
All these dependencies may be obtained by the package metadata using some kind of plugin architecture adapted
to the different existing tools (RPM/Apt etc.).
An interesting comparison of package metadata formats can be found in
Joey Hess' companion article to the
Alien package converter.
Examples of analysis:
- BasicCoherence : the graph does not contain any
- DanglingDependency.
(this happens a lot to Roberto in Debian, because of
some kind of indian curse that makes him put his feet
in every pitfall).
This looks, in principle, very easy, as it can be done
by just any kind of complete visit of the graph, but
we may step on some surprises, if you think of versions,
virtual packages and the like.
- UnsatisfiableDependency, that is, conflicts between packages
that are in the transitive closure of the dependencies of
a same package.
This seems harder (or at least, the complexity seems very high at first sight!)
- UpdateClosure : starting from any CoherentConfiguration C1 subset of the
DependencyGraph, we can reach any other CoherentConfiguration C2 via a ConfigurationUpdate …
This kind of analysis seem much harder, but it is an absolute priority in the project
- UpdateSelection : analysis of the _weighted_ ConfigurationUpdate paths between C1 and C2.
For example, if we need to install some marginal tool (like Spim) which was
introduced very late int he package collection, recompiling from sources
can be much more convenient than pulling all the necessary strings to make the
installation of the binary package available possible.
This is a very concrete example coming from Roberto's experience in this year's Compiler course.
Planning
We need to pursue three kind of efforts now:
(a) building a set of case studies by collecting many examples, from standerd to very byzarre,
in the current Package Management Systems, plus analysis of the relevant literature (seems not
to be thick, at all)
(b) design of the DependencyGraph model: this can lead to a trial and error phase in conjunction
with the algorithm design for the analyses
(c) prototype construction, including some subtasks like the plugin architecture to extract metadata from
the existing package management tools rpm/lsm/deb …
It would be nice if we could end up providing a tool being to rpm/apt etc. what mlDonkey is to the
specialised p2p networks.
The dependency order (a) -> (c) and (b) -> (c) is clear, but (a) and (b) might be done in parallel.
{metadata}
Topics Wp2
{metadata}
Comments: 0