Blog of Julian Andres Klode

Debian, Ubuntu, Linux in general, and other free software

Implicit preferences in OR dependencies

Debian packages commonly use or dependencies of the form “a | b” to mean that a or b should be installed, while preferring option a over b. In general, for resolving an or dependency, we will try all options from the left to the right, preferring the left-most option. We also prefer real packages over virtual ones. If one of the alternatives is already installed we use that.

def solve_or(or):
  best_real = None
  best_virtual = None
  for dep in or:
     for target in dep:
        if target.name == dep.name and best_real is None:
           best_real = target
        if target.name != dep.name and best_virtual is None:
           best_virtual = target        
        if target.is_installed():
          return target

  return best_real if best_real is not None else best_virtual

Now, this way of solving dependencies is slightly problematic. Let us consider a package that depends on: a | b, b. APT will likely choose to install ‘a’ to satisfy the first dependency and ‘b’ to satisfy the second. I currently have draft code around for a future version of APT that will cause it to later on revert unneeded changes, which means that APT will then only install ‘b’. This result closely matches the CUDF solvers and cupt’s solver.

On the topic of solving algorithms, we also have the problem that optimizing solvers like the ones used with apt-cudf do not respect the order of dependencies, rather choosing to minimise the number of packages installed. This causes such a solver to often do stuff like selecting an sqlite database as backend for some service rather then a larger SQL server, as that installs fewer packages.

To make such solvers aware of the implicit preferences, we can introduce a new type of dependency category: Weak conflicts, also known as Recommends-Not. If a package P defines a Recommends-Not dependency against a package Q, then this means that Q should not be installed if P is installed. Now, if we have a dependency like:

Depends: a | b | c

we can encode this as:

Recommends-Not: c, c, b

Causing the solver to prefer a, then b, and then c. This should be representable as a pseudo-boolean optimization problem, as is common for the dependency problem, although I have not looked at that yet — it should work by taking the standard representation of conflicts, adding a relaxation variable and then minimising [or maximising] the number of relaxation variables.

About these ads

Written by Julian Andres Klode

August 11, 2012 at 16:27

Posted in APT2, Debian, General

3 Responses

Subscribe to comments with RSS.

  1. Sounds like you’re recreating aptitude’s solver and its scoring system.

    Why not do this with a multi-pass algorithm? Select all the packages for installation that you absolutely *have* to, then satisfy all unsatisfied ‘|’-dependencies at increasing depth from the root until you’ve satisfied them all.

    Anonymous

    August 12, 2012 at 06:07

  2. Which, thinking more about it, will probably produce similar results to your “add then un-add” solver: you’d add all the first usable choices in each alternative, but then go back and remove any packages you can while still satisfying dependencies.

    Anonymous

    August 12, 2012 at 06:08

    • Aptitude produces the same result as APT, it installs those unneeded packages as well. The only solbers I saw that did not do this were cupt’s and the CUDF solvers (out of apt, aptitude, cult, CUDF ones).

      Julian Andres Klode

      August 12, 2012 at 08:45


Comments are closed.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: