Dependency resolution

7 min read

When you ask peipkg to install nginx, the request does not yet describe the full work. nginx needs other packages; those need others; some version of each has to be chosen; everything has to be installed in an order where a package's dependencies come before it. Turning the short request into that concrete, ordered plan is resolution, and it is the first thing every change command does.

Resolution is a pure calculation #

peipkg resolves from metadata alone — the package descriptions in the cached repository indexes and in installed packages' manifests. It does not download any .peipkg files to work out a plan. Downloading happens later, only once a plan is approved.

That makes resolution a pure calculation over three inputs — your request, the set of installed packages, and the set of available packages — and gives it a property worth relying on: it is deterministic. The same inputs always produce the same plan. The plan you inspect with --dry-run is the plan that will execute; nothing is re-decided between previewing and applying.

If a request cannot be satisfied — a dependency that no repository can provide, two requirements that contradict — resolution rejects it, with an explanation, before anything is fetched or changed.

The relationships between packages #

A package's manifest declares how it relates to others. Four relationships drive resolution.

Dependencies. A package can require other packages, each by a version range. peipkg pulls every dependency into the plan, and their dependencies in turn, until the request is closed.

Conflicts. A package can declare that it cannot coexist with another. If a plan would put two conflicting packages on the system at once, resolution rejects it.

Provides. Several packages can advertise the same capability — a virtual name that is not itself a package. A dependency written against that name is satisfied by any package that provides it. This is how "needs a mail transport agent" can be met by whichever one you actually install.

You can ask for a virtual name directly, too: peipkg install coreutils works even when nothing is named coreutils, and installs whichever package provides it. Because you asked for one name and got a package with another, peipkg says which one it chose. Upgrades and removals are the exception — those name a package you already have, so they match by name only and never substitute one package for another.

Replaces. A package can declare that it supersedes another — the usual case being a rename, or a merge of two packages into one. Installing a package that replaces another causes the replaced package to be removed as part of the same plan.

provides has a stronger cousin: a claim, a single shared name that exactly one package may hold at a time. Where any number of packages can advertise the same provides name at once, a claim has one holder — see Claims.

A dependency can also be routed into a different root, written Depends: foo IN <root>, so that a whole root can be composed through the dependency graph — see Named roots.

Choosing a version #

When more than one version of a package could satisfy the plan, peipkg chooses by a fixed rule:

1. Prefer the highest version that satisfies every constraint on that package.
2. When two repositories offer the same version, prefer the one with the stronger (lower-numbered) priority — see Repositories and trust.

When the candidates are competing to fill a virtual name rather than being versions of one package, "highest version" means the version each one advertises for that name, not its own. Two packages providing coreutils are unrelated software numbered on unrelated scales, so peipkg compares what each offers the role — otherwise the role would go to whichever project numbers its releases higher. If everything above still ties, package name order settles it, so the answer never depends on the order packages happened to be read in.

For an upgrade, the installed version anchors the search: peipkg looks for something newer and stays put if there is nothing newer to move to.

Optional dependencies are never chosen automatically. A package can suggest companions that are useful but not required; peipkg surfaces those as suggestions and leaves the decision to you. A plan only ever contains what is genuinely needed plus what you asked for.

The plan #

The output of resolution is the ordered list of operations you see at the proceed? prompt — installs, upgrades, downgrades, and removals, sequenced so every package's dependencies are in place before it.

A removal gets one extra step. peipkg first computes the reverse-dependency closure — everything that would be left needing a package you are removing — and either refuses the plan or, with --cascade, widens it to include them. That logic is covered in Installing and removing packages.

Resolution is also bounded. A dependency graph cannot be crafted to make peipkg search forever; the resolver works under a hard cap and gives up cleanly rather than hanging if a graph is pathological.

Elevated authorisation #

Most of a plan is routine, and the single proceed? prompt covers it. A plan can also contain an action that a routine yes should not cover — one you must review and approve individually, on its own.

peipkg detects three such actions and, for each one in a plan, asks a separate question:

this operation requires elevated authorisation:
  nginx would move backward from 1.27.5 to 1.27.4
authorise this specific action? [y/N]

The three actions that trigger it:

Two things make this prompt different from the routine one:

• --yes does not satisfy it. --yes skips the routine proceed? prompt; it has no effect on an elevated-authorisation question.
• It fails closed. With no terminal to answer on — an unattended script, a pipeline — there is no answer, so the action is not authorised and the operation is cancelled. An elevated action is never authorised by default.

Each elevated action is presented and authorised on its own; approving one does not approve the next. And the authorising act is itself written to the audit stream — the record shows not just what was done, but that it was specifically authorised and what was authorised.

If an elevated action is not one you want, the plan as a whole is the thing to reconsider: where the package is coming from, whether the repository priorities are right, whether the downgrade is really what you meant.

Where to go next #

For the flow that presents and applies the plans resolution produces, read Installing and removing packages.

For the single-holder extension of provides, read Claims.

For the repository priorities and trust states resolution consults, read Repositories and trust.

Edit this page