Three different optimization criteria will be used. All three are lexicographic combinations of different measurements which we describe below.
Note that each of these measurements calculates an integer value only from the initial and the final installation status, that is the user request to install or remove a certain package is not used here. The reason is that each proposed solution must first of all satisfy the user request, otherwise it will be discarded and the solver will obtain a penalty value. Only those proposed solutions that actually are solutions will be compared by the optimization criteria defined below, yielding a score according to the ranking obtained. This is more precisely described in the ranking rules.
For the third ("full user") criterion we will make use of an extra package property which is not among the mandatory package properties. This additional property is recommends, and it has values of type vpkgformula (that is the same type as the mandatory property depends). The idea is that recommended packages are non-mandatory dependencies.
For that reason, the CUDF documents will contain a specification of that property in the document preamble, like this:
preamble:
property: recommends: vpkgformula = [ true! ]
The measurements that we will describe below are taken on selected sets of packages in order to measure the quality of a proposed solution. Package sets are denoted by the following constant expressions:
solution, new, removed, changed. up, down
Basic sets are expressed using only solution, new, changed and removed.
Given an initial universe I and a proposed solution S, each of these constant expressions denotes a set of packages. In the following we write p.f for the value of property f in package p. If X is a set of packages then X.f denotes the set of values of packages in X under property f. For instance, I.name denotes the set of names of packages that are initially installed.
Example: The following table illustrates these definitions, The first two lines define I and S, the remaining ones show the sets calculated from these:
package name | a | b | c | d | r | s | t |
---|---|---|---|---|---|---|---|
versions in I | 2 | 3 | 5 | - | 4, 6 | 4,6 | 4,6 |
versions in S | 3 | - | 5 | 1 | 3, 7 | 5 | 5,7 |
versions in solution | 3 | - | 5 | 1 | 3, 7 | 5 | 5,7 |
versions in changed | 2,3 | 3 | - | 1 | 3,4,6,7 | 4,5,6 | 4,5,6,7 |
versions in new | - | - | - | 1 | - | - | - |
versions in removed | - | 3 | - | - | - | - | - |
versions in up | 3 | - | - | - | 7 | - | 7 |
versions in down | - | - | - | - | 3 | - | - |
Measurements are terms that are evaluated to an integer value. They are always constructed as a function applied to a set of packages (this set will be one of the sets solution, changed, new, removed defined above) plus possibly additional arguments. More exactly, a measure is a term of one of the forms
count(X), sum(X,f), unsat_recommends(X), aligned(X,g1,g2), notuptodate(X)
where X is a set of packages, f a property of type int or one of its subtypes, and g1 and g2 any properties. These properties may be core properties defined in the CUDF specification, or properties that are declared in the preamble of the CUDF document. Basic measurements are measurements built using only count or sum.
Measurements are evaluated as follows. Note that some of the definitions make use of the set S (the solution) or U (the universe, that is the set of all known packages):
A typical example of this would be sum(solution,size), where size is an additional integer-valued property of packages indicating their size.
For instance, if package a recommends
b, c|d|e, e|f|g, b|g, h
and if S installs a, e, f, and h, but neither of b, c, d, or g, then one would obtain for the package a alone a value of 2 for unsat_recommends since the 2nd, 3rd and 5th disjunct of the recommendation are satisfied, and the 1st and 4th disjunct are not. If no other package in X contains recommendations that means that, in that case, unsat_recommends(X)=2.
The properties g1 and g2 may only have type int or string.
<p/>
There are several applications for this:
<ol>
<li> aligned(solution,package,version) is the number of multiple
versions of installed packages: a package installed in
only one version counts 0, and a package installed in n different
versions counts n-1.
<p/>
For instance, if the <kbd>solution</kbd> is
S={(a,1), (a,2), (a,3), (b,1), (b,2)} then the first set of
clusters by (package,version) would be the same as S of
cardinality 5, and the second set of clusters by package name only
would be {a,b} of cardinality 2, yielding a result of 5-2=3.
</li>
<li> aligned(solution,sourcename,sourceversion) is
the number of <i>version changes</i> as defined in the paper
<a href=http://eptcs.org/paper.cgi?LoCoCo2011.1>Aligning
component upgrades</a> by Di Cosmo, Lhomme, Michel at LoCoCo 2011.
</ol>
The criteria used in the three tracks are
lex( min removed, min changed)
Hence, two solutions S1 and S2 will be compared as follows:
The timeout for this track is 30 seconds. The signal SIGUSR1 is sent
approximately 5 seconds before the timeout.
Hence, in this track we use only sets build with solution, new, changed and removed, and we use only measurements build with count and sum.
For instance, the paranoid criterion of the first track could be written as
-count(removed), -count(changed)
The timeout for this track is 150 seconds. The signal SIGUSR1 is sent approximately 10 seconds before the timeout.Hence, in this track we use sets build with solution, new, removed, changed. up, down; and we use measurements build with count, sum, unsat_recommends, aligned, and notuptodate.
For instance, a user of a machine with a small disk might write
-count(removed),-sum(solution,installedsize),-notuptodate(solution),-unsat_recommends(solution),-count(new)
The timeout for this track is 300 seconds. The signal SIGUSR1 is sent approximately 10 seconds before the timeout.