Libzypp/Solver/Implementation

From openSUSE

This page is work in progress. It will be expanded as time permits. For specific questions, please ask the author.

Dependency Solver 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

Functional Blocks

The solver operates with three major functional blocks.

1. the ResolverQueue containing upcoming tasks
2. the ResolverContext containing the current transaction (already computed install and remove requests)
3. the ResolverInfo containing the log of the already computed tasks

The tasks inside the ResolverQueue are represented as objects derived from QueueItem.

ResolverQueue

The ResolverQueue is a linked list of yet-unhandled QueueItems.

The Resolver::resolveDependencies() function runs ResolverQueue::process() until ResolverQueue::isEmpty().

Processing a QueueItem often results in new QueueItems which are appended to the current queue. The typical case is an install request resulting in additional requirements to be fulfilled.

The queue fill rate acts like a gauge during dependency resolving. Solving stops when the queue is empty or an error occurs.

ResolverContext

As the solver goes along processing QueueItems, resolvables change their state. Uninstalled ones will be scheduled for installation, installed ones scheduled for removal, those conflicting with a to-be-installed one are impossible to install.

All these state changes are recorded in the ResolverContext. Every time the solver wants to know the state of a resolvable, it goes through the context. The context gives the future view of the system.

ResolverInfo

Every ResolverContext stores information about the process of the current solver run. This information is a list of ResolverInfo entry. All these entries are stored as a linked list (via ResolverContext::addInfo()) and accessible through an iterator (ResolverContext::foreachInfo())

ResolverInfo contains following information:

• kind of info (e.g. RESOLVER_INFO_TYPE_CONFLICTS_WITH,RESOLVER_INFO_TYPE_OBSOLETES,RESOLVER_INFO_TYPE_DEPENDS_ON)
• affected resolvable
• priority of the info (integer)
• flag if this info reports an error. An error will be regarded while evaluating solutions for solver problems.

ResolverInfo will not be used in libzypp but classes which are derived from ResolverInfo which have additional information:

• ResolverInfoContainer derived from ResolverInfo

  Contains an addition resolvable list of involved items (e.g. foo is needed by bla. Foo is the affected item in ResolverInfo while bla is a list member of the additional resolvalbe list)

• ResolverInfoObsoletes derived from ResolverInfoContainer

  foo will be obsoleted by bar

  ResolverInfo type: RESOLVER_INFO_TYPE_OBSOLETES

• ResolverInfoNeededBy derived from ResolverInfoContainer

  foo will be needed by bar

  ResolverInfo type: RESOLVER_INFO_TYPE_NEEDED_BY

• ResolverInfoMissingreq derived from ResolverInfo

  Requirement bar (access via ResolverInfoMissingReq::capability()) cannot not be fullfilled which will be required by resolvable foo.

  ResolverInfo type: RESOLVER_INFO_TYPE_MISSING_REQ

• ResolverInfoDependsOn derived from ResolverInfoContainer

  Resolvable foo depends on bar which will be deleted.

  ResolverInfo type: RESOLVER_INFO_TYPE_DEPENDS_ON

• ResolverInfoConflictsWith derived from ResolverInfoContainer

  Resolvable foo conflicts with resolvable bar via the capability xyz ( access via ResolverInfoConflictsWith::capability() )

  ResolverInfo type: RESOLVER_INFO_TYPE_CONFLICTS_WITH

• ResolverInfoChildOf derived from ResolverInfoContainer

  not used

  ResolverInfo type: RESOLVER_INFO_TYPE_CHILD_OF

• ResolverInfoMisc derived from ResolverInfoContainer
  It is a common class which has additional members:
  • action (string, not used)
  • trigger ( Triggereason: NONE CONFLICT, OBSOLETE, REQUIRE) (e.g.: erasing caused by OBSOLETE)
  • capability
  • second capability
  • second affected resolvable
    The last three members will be needed for e.g. RESOLVER_INFO_TYPE_CONFLICT_CANT_INSTALL ( foo provides bar1 which conflicts with foo2 which provides bar2)

QueueItem

QueueItemInstall

installs/updates a resolvable

If another resolvable with the same name already exists, the install is treated as an upgrade. An upgrade triggers an uninstall reuqest for the installed resolvable

install will

• Prevent "self" update.
• Check if this installation is still needed by other resolvables ( if it will be installed due a requirement only).
• Generate a QueueItemUninstall for the resolvable which will be updated.
• Trigger require tasks for each 'requires' dependency if it is not already satisfied.
• Trigger soft-require task for each 'recommends' dependency.
• Trigger conflict tasks for each 'conflicts' dependency.
• Trigger conflict tasks for each 'obsolete' dependency.
  Obsolete dependencies are handle like conflicts in the solver.
• Trigger estalish tasks for each 'freshens' dependency by going over each provides of the to-be-uninstalled item.
• Trigger estalish tasks for each 'supplements' dependency by going over each provides of the to-be-uninstalled item.

QueueItemUninstall

uninstalls a resolvable

• If this request has been generated by the solver themselves( due unsatisfied dependencies ) an error and additinal information will be generated for showing the problem.
  (in ResolverContext::uninstall())

• Loops over all provides of the resolvable and find out if there are any installed resolvables which still require any of the provided capabilities.
  If yes, the uninstall might break a dependency.
  • If there are other installed resolvables providing the same capability, we're done.
  • If not, a new QueueItemRequire will be generated in order to solve this unsatisfied dependency

• Loops over all provides of the resolvable and re-establish all resolvables which 'freshens' or 'supplements' match these provides.
  (by generating a new QueueItemEstablish entry).

• If the resolvable is a 'Patch' all concerning 'Atoms' will be deleted too by generating a new QueueItemEstablish' entry.

• If the resolvable will not be updated and it is not a Package: Delete all installed resolvables which will be recommended by the deleted resolvable. (Generating a new QueueItemEstablish entry).

QueueItemRequire

Fulfills a required capability.

• Find a resolvable providing the required capability and schedule this for installation.
  Do not if the requirement is caused by a resolvable which will be deleted.
  In the first run find resolvables which are already selected for installation, or find resolvables with the best architecture and version.
  The other "fitting" resolvables will not be regarded in order to minimize branches. If the solver comes to none solution the other possibilities will be regarded too.
• Found none providing resolvable.
  • Try to upgrade the resolvable which requires this dependency OR
  • Delete this resolvable if none provider is available. This will cause an error message to the user.
• Found one providing resolvable.
  Install this resolvalbe.
• Found more than one resolvable.
  If multiple resolvables are possible, create a branch task with multiple install requests.

QueueItemConflict

There are two kinds of conflicts:

• Resolvable "foo" conflicts via dependency "bar" with resolvalbe "foo2" which provides "bar".
• Resolvable "foo" obsoletes "bar". "bar" will be provided by "foo2". So "foo2" conflicts with "foo".

There are two possibilities to solve a conflict:

• Update the conflicting resolvable if the updated resolvable has not this conlict anymore.

• Delete the conflicting item:
  Depending on the conflicting resolvable(s) it
  • schedules the conflicting for removal (if its installed) (This will result to an user error if the conflict is not an obsoleting conflict)
  • sets its status to impossible (if its uninstalled)

QueueItemConflict is only created if a to-be-installed resolvable has a conflicts dependency.

QueueItemBranch

For each task contained within, branch off a ResolverContext and Resolverqueue and compute each task in its own scenario.

e.g.: Package foo requires bar. This dependency will be provided by more than one package. So we will have to evaluate all possibilities. For all these possibilities one QueueItemBranch element will be generated which includes additional QueueItemInstall entry for each possiblities. This happens in the QueueItemRequire element where "foo requires bar" will be processed.

The main task of an element of this class is to store all possible QueueItems which fulfill this requirement and evalute unneeded branches which will not have to be regarded by the solver.

Splitting off this pool of possible QueueItems into own resolver queues will be managed in ResolverQueue and not in the class QueueItemBranch.

QueueItemEstablish

compute establish state

• Loop through all freshen dependencies of the resolvable. If none is satisfied (requirement is met) set it to unneeded and return.

• If we have freshens and supplements and at least one of the freshen deps were met, we look at its supplements as an additional condition (freshens AND supplements must be true. true means either empty or at least one match).
  If none of the supplements met, set the resolvable to unneeded and return.
  If one of the supplements were met install the resolvable and return.

• If we have no supplements and met freshens we look at its requires to set it to satisfied or incomplete.
  So the current code checks all requirements and only triggers an install of packages if
  • all requirements are already fulfilled
  • the package is not already installed (so we do only fresh installs, no upgrades here)

  For other kind of resolvables (e.g. Patches, Atoms), we now look at their requirements and set their state modifier accordingly.

QueueItemGroup

not used

(used in libredcarpet to group multiple tasks into one transaction)

Interface with rest of Libzypp

The interface between the solver and the rest of libzypp is described in Resolver.h.