Test of the Oz environment

Test of the Oz environment

We have verified that the Oz compiler is able to read succesfully program sources containing up to 10000 different constraint variables.

That should be enough for most of our applications.

Brainstorming on the formalization of the static analysis of the package repositories

The simples static analysis

As seen in the latest meeting, it is unreasonable to try and find unisntallable packages by an enumeration of all possible package configuration (over 20000 packages may be available at a given time, being most of the time loosely coupled).

We propose the following strategy:

• preprocess the list of available packages in order to replace complex version numbers by integers
• build a data structure that describes the dependency graph inside the Oz program
• for each available package P and version v, dynamically generate from this data structure

a set of constraints describing the interdependencies and conflics among all the packages which may be needed to install version v of P, and ask the Oz solver for a solution. In case no solution is available, we declare version v of P "broken".

This should work because we believe that the dependency graph is shallow and loosely coupled, but this hypothesis needs to be verified.

More complex analysis

A more complex problems is to find all versions v of a package P that may "break" previously existing "consistent installations".

What does this mean?

A "consistent installation" I is any set of packages which can be installed together, with all dependencies resolved (i.e. if P is in I, then all Q s.t. P depends on Q belongs to I, and all R s.t. P conflicts with R is not in I, of course, with the relevant version information taken into account).

We say that a package P, version v, breaks I if

• I contains a previous version of P
• either one of the following is true
• there is no way to upgrade the packages of I to the point of getting a consistent installation I' that

contains P version v, and still contains all the packages of I (maybe at higher versions, or, emitting a warning, at lower version 8 vs 7?), taking into account the Replaces: metadata information (see note below about Replaces:).

• B.: this is a very strong requirement!? there exists a package Q which is installable in I, but is no longer installable in any I' reached after

installing version v of P

To find all version of a package that may break an existing installation, we could proceed naively as follows:

build all installations I from the package repository (exponential)

(if we accept the strong requirement in the definition, it will be enough to find all maximal I) 2 try to "install" version v of P in I, and see if it is possible without violating the conditions above. (if we take maximal I's, the two conditions are equivalent)

This is largely exponential, AND it is also largely suboptimal, because, again, the graphs we handle are loosely coupled and shallow.

Looking for a smarter strategy

Using the properties of the graph, we may hope to obtain much better results, even if we still do not know HOW to do it.

Here follow some observations, open problems:

Observation If I is broken by upgrading P from k to k', this means that version k' has some differences in the depencies/conflicts metadata, and in particular, the constraint for k does not imply the constraint for k'

Can we exploit the differences to find the maximal set of packages impacted by this difference?

Open problem It seems that we need to come up with an algebra of dependency constraints, allowing us to perform (possibly compositional) manipulations of sets of dependency constraints.

For example, if we write #P for "the set of (package, version) incompatible with at least one (package,version) in P", is there a compositional way of computing #P?

This means, if P=P1 union P2, can we (efficently) compute #P from #P1 and #P2? It may be the case that to do this we also need to build D(P), D(P1) and D(P2) where D(P) means the set of packages "needed" to install P.

It is not clear that this may be done, in particular because of the disjunction operator in the dependency language, that seems to allow very strange ways of building incompatibilities when taking P1 union P2:

Fact it is the case that #(P1 union P2) contains #P1 and #P2, but the converse is not true: example

• p1 wants q>3, p2 wants q<2 … then q is not in #p1 nor in #p2, but it is in #(p1 union p2)
• p1 maybe installed with q, but choosing an or branch that imposes r>3, p2 may be installed with q,

but choosing an or branch that imposes r<2 (same as above)

Luminous idea (Ralf's) change the definition of #P to "the set of sets of packages that are incompatible with P"

Notice that, to cut down the search space, it may be reasonable to pinpoint the "relevant" packages by means, for example, of a system of priorities...

• • Main.RobertoDiCosmo - 14 Mar 2005