Libzypp/Solver/Implementation/BigPicture

From openSUSE

Dependency Solver - the big picture

The dependency solver divides its task - one or more install, update, or remove requests - into small, manageable steps and processes them in a queued fashion.

Processing queued tasks

Main components

This architecture has the following main compoments:

• QueueItem
  Represents the base class for a task. Specific tasks are derived from it - see below
• ResolverQueue
  Provides a FIFO queue for the QueueItems
• A process engine
  Picks the next QueueItem from the ResolverQueue and processes it.

Processing is actually a per-QueueItem method as it is specific to the task performed by the QueueItem.

As a result of the processing, zero or more new QueItems might be created, resulting in more work.

The processing continues until the ResolverQueue is empty. (Thats a simplified view, see below for the details).

ResolverContext

The processing step is done within a specific ResolverContext which is attached to ResolverQueue being processed.

The ResolverContext shows the transaction, it lists those resolvables which change state (from uninstalled to installed or vice versa).

Context is per QueueItem

Each ResolverQueue is processed within its own context. For non-ambiguous dependency resolutions, this is not strictly needed as there will be a single solution. However, as soon as multiple alternatives come into play, the per-ResolverQueue context is required.

ResolverContext and branching

The picture to the right shows three ResolverQueues awaiting processing. The one with the green QueueItems is part of a transaction where three package changes are already set - one install (ins) and two deletes (del). The ones with the blue and red QueueItems are alternatives based on this transaction, trying to install different versions of 'geeko'. Alternatives - also called branches internally - don't copy the complete ResolverContext but branch off at a specific point. Each ResolverContext has a parent pointer pointing either to another ResolverContext (in case of branch) or to NULL.

Getting status

Querying the status of a resolvable (installed or uninstalled) can either go through the ResolverContext or the resolvable.

Going through the resolvable will give the current, before transaction status.

Going through the ResolverContext gives the future, after transaction status.

ResolverContext::getStatus() is used to determine the status of a resolvable. It first looks if the resolvable is listed in the current context. If not, it follows the parent pointer and calls getStatus() of the parent ResolverContext.
If there is no parent (NULL pointer), the resolvable is checked.

A resolvable is installed if its listed as a member of the '@system' catalog. A resolvable is uninstalled if its listed as a member of any other catalog.

ResolverQueue processing

Processing QueueItems from the ResolverQueue is a bit more sophisticated than described above. Actually, processing is splitted between Resolver::resolveDependencies() and ResolverQueue::process() and involves multiple queues.

Processing a queue iterates over all QueueItems in the queue but pushes new QueueItems into a new ResolverQueue which, at the end of the iteration, replaces the original queue. This way, QueueItems from before the process step and QueueItems resulting from the process step are never mixed. But ResolverQueue::process() keeps working until the queue is either empty or an error (dependency problem) was detected.

The Resolver itself keeps multiple ResolverQueues in order to handle different branches (dependency solution alternatives) and queues without a solution.

There are five queue buckets defined within the Resolver:

• 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)

QueueItems

There are the following derived QueueItem classes defined:

• Libzypp/Solver/Implementation#QueueItemInstall
  Install a specific, uninstalled resolvable
• Libzypp/Solver/Implementation#QueueItemRequire
  Find resolvables matching a specific capability
• Libzypp/Solver/Implementation#QueueItemUninstall
  Remove a specific, installed resolvable
• Libzypp/Solver/Implementation#QueueItemConflict
  Handle a conflicts dependency from a to-be-installed to an installed resolvable
• Libzypp/Solver/Implementation#QueueItemBranch
  Handle multiple alternatives for a dependency resolution (i.e. multiple packages matching a capability)
• Libzypp/Solver/Implementation#QueueItemEstablish
  Handle freshens and other reverse dependencies
• Libzypp/Solver/Implementation#QueueItemGroup
  Handle multiple requests as one (ported from libredcarpet but unused in ZLM7)

Update Example with Architecture Change

Update MozillaFirefox.2.0.i586 --> MozillaFirefox3.0.x86_64

MozillaFirefox.2.0.i586 requires libstartup.so

MozillaFirefox3.0.x86_64 requires libstartup.so(64bit)

startup-notify-32bit.x86_64 provides libstartup.so (installed)

startup-notify.i586 provides libstartup.so (not installed)

startup-notify.x86_64 provides libstartup.so(64bit) (not installed)

First Solver Run

   Delete startup-notify-32bit.x86_64 cause it is unsupported
   Add an unfulfilled requirement libstartup.so for MozillaFirefox.2.0.i586

   Install MozillaFirefox3.0.x86_64
   Add a delete request for MozillaFirefox.2.0.i586
   Add requirement of libstartup.so(64bit)

Second Solver Run

   Requirement libstartup.so
   Installation Request for startup-notify.i586

   Requirement libstartup.so(64bit)
   Installation Request for startup-notify.x86_64

   Delete MozillaFirefox.2.0.i586
   Removing MozillaFirefox.2.0.i586

Third Solver Run

   Install startup-notify.x86_64 due the need of MozillaFirefox3.0.x86_64

   Install startup-notify.i586 due the need of MozillaFirefox.2.0.i586

That would generates an error (parallel installation of packages). The solver checks in the installation requests (third run) if the requirements still exists. (Has been MozillaFirefox.2.0.i586 removed meanwhile).