Libzypp/Solver

From openSUSE

Dependency Solving

Solving dependencies is the core functionality for any software management application on Linux.

Software Management/Dependencies are used to divide and share functionalities across multiple software elements.

Linux (and Unix) follow two basic concepts to implement Divide & Conquer - breaking a large problem into smaller, more manageable ones.

• Make each program do one thing well. See Basics of the Unix Philosophy for details.
• Use shared libraries to share implementations and save disk and memory space

Every software package expresses the functionalities it provides to others and those it requires from others through dependencies.

The task of the dependency resolver is to check and fulfill all these relations when managing software.

Basic laws of resolving

The dependency solver tries to solve dependencies without user intervention based on two basic rules

1. Fulfill the install/remove requests given at start
2. Keep the (dependencies of the) installed system consistent

Since the solver treats every package alike, these rules have some major and sometimes unexpected implications. A broken dependency might result in removal of lots of packages - the resulting system is still consistent by highly unusable.

Implementation

The dependency solver is a C++ port of Ximians red carpet solver (which is written in glib/gobject).

Its source is available in the libzypp subversion repository

The big picture

The architecture of the solver is best explained in a big picture

Use Cases

The details of the implementation are best described by going through some typical use cases:

• Installing a package
• Removing a package
• Updating a package
• Handling conflicts
• Handling obsoletes
• Verify system

Details

See solver implementation for more details about the inner workings.

Branching

Branching is used to compute several solutions in case if multiple possibilities exist to solve a specific dependency (resp. solver task).

See branching for details.

Solutions

Solutions are represented by resolver queues which have different status:

• pending queues
  These are active queue awaiting processing.
• completed queues
  These are completed solutions. The queues only contain a context.
• pruned queues
  These are alternative solutions which are equal or worse to solutions in 'completed queues'
• deferred queues
  These are branches which will only be considered (moved to 'pending') if there are no solutions yet.
• invalid queues
  These are queues without a solution (dependency error)

Only the completed and invalid queues are interesting. If no valid result has been found the solver takes the first entry of the invalid queue and generates problem descriptions and solutions. If the completed queue is not empty the solver tries to find out the best solution by comparing each completed queue entry with each other.

See solutions for details.

Each solution has resolvables with their corresponding status. This status can be found in the logfiles of libzypp:

e.g.

Resolver.cc(show_pool):913 180: I_TsU[S1:0][package]zmd-7.1.1.0-39.49.i586
Resolver.cc(show_pool):913 186: I_TsU[S1:0][package]yast2-online-update-2.13.43-1.2.noarch
Resolver.cc(show_pool):913 188: I_TsU[S1:0][package]yast2-online-update-frontend-2.13.43-1.2.noarch

The interesting part is the bitfield (e.g. I_TsU) which has following format:

1. StateField Whether the resolvable is installed or uninstalled (available).
   • I installed
   • U uninstalled (available)
2. EstablishField Established status computed by the solver as unneeded (have freshens but none of them trigger) satisfied (no freshen or at least one triggered freshen and all requires fulfilled) or incomplete (no freshen or at least one triggered freshen and NOT all requires fulfilled)
   • U unneeded
   • I incomplete
   • S satisfied
   • _ undetermined
3. TransactField Wheter to transact this resolvable (delete if installed install if uninstalled). In case the resolvable is locked, only USER may modify the transact bit.
   • T transact
   • _ keep
   • L locked
4. TransactByField Who triggered the transaction. Transaction bit may be reset by higer levels only.
   • u by user
   • h by application high
   • l by application low
   • s by solver
5. TransactDetailField Reason why the Resolvable transacts. Splitted into InstallDetailValue and RemoveDetailValue dependent on the kind of transaction.
   • O is to be uninstalled due to obsolete
   • L is to be uninstalled due to unlink
   • U is to be uninstalled due to upgrade
   • _ is to be installed soft
   • @ is seen
   • X is impossible

Known Problems

• No repository priorities
• No good update all algorithm.
• Behaviour should be more configurable.
• The problem solutions should be more verbose and understandable for the user
  • Add more information into Problem-Solution-Datails ( extracted from ResolverInfo ).
  • "Translate" error message concerning Atoms in an user readable message
  • Give more information about "This package has been selected by the requirement of these packages.". Or "This package will cause the installation of these additional packages."
• Dynamic dependencies like conditional dependencies or filesystem dependencies will not be handle correctly cause there is no machanism (e.g. signal handling) in the solver.
• Proper support of SuSE-Plugger and additional Add-On-Produkts concerning hardware and languages.
• Reverting recommended package installation if dependencies are not fulfilled.
  e.g. Recommended package foo1 requires foo2 which requires foo3 which requires foo4. The last requirement foo4 is not fulfilled so the user is getting an error message. Desired behaviour: foo1, foo2 and foo3 will not be installed and the user will not be informed cause it is a recommended installation only.
• Proper behaviour of erasing patterns
  Current behaviour: Delete all packages which are recommended by the pattern.
  There are three possibilities which has to be decided by the user:
  • Delete the pattern only ( remove the "attribute" only e.G. the system is a print server)
  • Delete packages which are required/recommended by this pattern only. Do not delete packages which are recommended by another patterns too.
  • Delele all packages which will be shown on the right side of the single package selection.

Future

The current solver operates on concrete objects, specifying exact package versions and repositories. This limits its possibilities in finding the best solution.

Future versions of the solver should operate on capabilities instead, describing the expected result of the solving operation.

Differences to pre 10.1 versions

See here on what changed compared to SUSE Linux versions before 10.1