In the Closure of Madness: Spec-based Package Management with Closure-Sanity Validation

Introduction

Linux distributions split their software into packages, which together with the kernel compose a full operating system. The usual way to assemble the packages into a system is the distribution's package manager, which requires superuser privileges and a host system of the same distribution family, meaning a Debian filesystem can only be built from a Debian system. The package formats themselves impose no such requirements, since they are public specifications, and a program that follows them can build the same filesystem on any Linux system as a regular user.

In this article, we present a methodology for root filesystem initialization without superuser permissions or an existing package manager, implemented as a tool called FlatRoot. We start by exploring the packaging formats of four popular distributions, those being Debian, Fedora, Arch Linux, and Alpine. We then present the resolver, which walks the dependency graph to build the closure of package dependencies. Following, we present the post-extraction steps, which compose a sane root filesystem. Lastly, we validate the resolver against the package managers of each distribution, the validation process checks the packages of the expected closure against the real output of the package managers.

Background

In this section, we introduce the basics of package management across Linux distributions. We start with the concepts common to the different implementations and the process that a package manager does to create valid root filesystems (known as rootfs). Lastly, we describe the distinct archive formats each package manager uses to manage root filesystems.

A package is an archive that the package manager downloads from the distribution's repositories and installs onto the system. Across all four families in this article, it is built from the same parts:

The archive: the files that the package installs on the root filesystem, stored in the expected target directory layout.
Metadata: the package name, version, and its relationships to other packages, such as dependencies and conflicts.
Maintainer scripts: executable hooks that run at installation time to finish configuration (Debian Policy 6, alpm-install-scriptlet, apk's install hooks per apk-v2(5)).

A package manager orchestrates these parts into a working system, and it starts from the metadata. A request rarely stops at the package it names: bash needs the C library libc6 and the terminal library libtinfo6, and each of those needs packages of its own. The package manager follows every dependency, then the dependencies of those dependencies, until no new package appears. The resulting set is the coind as the dependency closure of the request: it contains the requested packages, and every dependency satisfied recursively. The package manager downloads and extracts the archives of every package in it, followed by the post installation scripts.

Each package manager has distinct archive formats with their own disposition of data. Debian packages its software as .deb files, a format it shares with Ubuntu and the many derivatives of both, with the tooling split in two layers:

dpkg installs individual .deb files onto the system
apt sits above it to fetch packages from repositories and resolve their dependencies.

The format is specified in the Debian Policy Manual, which defines the metadata and the rules around it, and dpkg's manual pages, which enforces the spec of the distributed archive.

The RPM Package Manager and its .rpm package format uses the same two-layer split: rpm installs individual files onto the system, and dnf, or zypper on openSUSE, fetches packages from repositories and resolves their dependencies, per rpm's reference documentation. Arch Linux and its derivatives package their software as .pkg.tar.zst files, handled by pacman, a single layer covering both aforementioned roles with ALPM (Arch Linux Package Management) library, with makepkg producing the archives, per the ALPM specifications. Alpine Linux packages its software as .apk files, handled by apk, a single layer from index fetch to extraction, per the apk-tools documentation, with v2 as the current stable version; apk-tools 3 defines a successor v3 format based on a different container (apk-v3(5)), which this article does not cover.

Indices

In this section, we explore mechanisms of package distribution, the catalog that maps every package to its archive and metadata. Each family publishes its index in its own format, and this section walks through each.

Debian

Debian's index⁴ is the Packages file. It is a regular file, plain text: the index is a sequence of records, one per package, each a block of Key: Value lines and separated from the next record by a blank line. Inspecting it is reading text like any other file, xzcat Packages.xz | less pages through the file, and xzcat Packages.xz | grep '^Package:' lists the package names alone. The file is sorted alphabetically:

Package: 0ad
Source: 0ad (0.27.0-2)
Version: 0.27.0-2+b1
Installed-Size: 54427
Maintainer: Debian Games Team <pkg-games-devel@lists.alioth.debian.org>
Architecture: amd64
Depends: 0ad-data (>= 0.27.0), 0ad-data (<= 0.27.0-2), 0ad-data-common (>= 0.27.0), 0ad-data-common (<= 0.27.0-2), libboost-filesystem1.83.0 (>= 1.83.0), libc6 (>= 2.39), ...
Pre-Depends: dpkg (>= 1.15.6~)
Description: Real-time strategy game of ancient warfare
...
Filename: pool/main/0/0ad/0ad_0.27.0-2+b1_amd64.deb
Size: 15478892
SHA256: 704dae7df79a35ed1bd3a0a8d5d1b9ce7a4ecdef74ddff72114d9523d63710eb

Package: 0ad-data

Its records follow the syntax defined in Debian Policy 5.1: Key: Value fields, one record per package, with continuation lines beginning with a space or tab.⁵ The record for the bash package:

Every combination of release, component, and architecture has its own copy, served compressed at a fixed path such as dists/bookworm/main/binary-amd64/Packages.xz, and the package archives it points to live under the pool/ directory.

A mirror is a server that keeps a copy of the repository and serves it to clients in place of the central host, so a client downloads from a nearby server, which is faster and spares the central hosts the load. Every mirror serves the same layout. The project's own entry point is deb.debian.org, a host that serves the nearest mirror, so a client can name it in sources.list without picking one. The worldwide mirror list groups every official mirror by country, and the complete list lists them all. The mirror status page tracks how current and reachable each listed mirror is.

Walkthrough: the Debian index in FlatRoot

The Packages file describes everything Debian publishes. FlatRoot processes it into a local database of packages, and this walkthrough follows the processing from download to storage. The processing triggers when a command first needs the database: the install command opens its per-architecture context, the context populates the database on first use, and the population is dispatched to the format's backend, which for Debian is index_fetch.

src/pkg/deb.rs#L38-L48

let path_packages = format!("{path_dir_suite}/{component}/binary-{arch_str}/Packages.gz");
let (bytes_packages, mirror_origin) = repo
  .mirrors
  .fetch_with_origin(&path_packages)
  .with_context(|| format!("Packages.gz for {}", repo.label))?;

let mut decoder = flate2::read::GzDecoder::new(&bytes_packages[..]);
let mut text_packages = String::new();
decoder.read_to_string(&mut text_packages)?;
let packages = DebFormat::catalogue_parse(&text_packages, Some(&mirror_origin))?;
writer.packages_insert(packages, &crate::version::DpkgVersionCompare)?;

The first step is to fetch the remote file: its fixed path is assembled from the suite, the component, and the architecture. Packages.gz is downloaded from that path through one of the repository's mirrors. The file is compressed, so FlatRoot decompresses it into the plain text of the index and hands the text to catalogue_parse.

src/pkg/deb.rs#L126-L153

fn catalogue_parse(text: &str, url_prefix: Option<&str>) -> Result<Vec<Package>> {
  let mut packages: Vec<Package> = Vec::new();
  let mut current: Option<PackageBuilder> = None;

  for line in text.lines() {
    if line.is_empty() {
      Self::block_flush(&mut current, url_prefix, &mut packages)?;
      continue;
    }

    if let Some(ref mut builder) = current {
      if line.starts_with(' ') || line.starts_with('\t') {
        continue;
      }

      if let Some((key, value)) = line.split_once(": ") {
        builder.set(key, value);
      }
    } else if let Some((key, value)) = line.split_once(": ") {
      let mut builder = PackageBuilder::default();
      builder.set(key, value);
      current = Some(builder);
    }
  }

  Self::block_flush(&mut current, url_prefix, &mut packages)?;
  Ok(packages)
}

The fetched index is plain text, while the resolver works on individual packages and their fields, so the packages must be extracted from the text. This is the job of catalogue_parse, which iterates the text line by line. A record is a group of Key: Value lines, ended by a blank line, and each record describes one package. From every record, FlatRoot keeps the fields the resolver uses and ignores the rest.

src/pkg/deb.rs#L159-L173

fn block_flush(
  current: &mut Option<PackageBuilder>,
  url_prefix: Option<&str>,
  packages: &mut Vec<Package>,
) -> Result<()> {
  let Some(builder) = current.take() else {
    return Ok(());
  };
  let Some(mut pkg) = builder.build()? else {
    return Ok(());
  };
  PackageBuilder::url_prefix_apply(&mut pkg.filename, url_prefix);
  packages.push(pkg);
  Ok(())
}

The kept fields assemble a Package, one entry of the package database. Before the entry is saved, the Filename field is completed: its value, pool/main/0/0ad/0ad_0.27.0-2+b1_amd64.deb for 0ad, is only the suffix of the archive's URL, and the missing prefix is the mirror that served the index, for example https://deb.debian.org/debian. FlatRoot saves the two joined, https://deb.debian.org/debian|pool/main/0/0ad/0ad_0.27.0-2+b1_amd64.deb, and the installation process uses this value to download the archive from its full URL.

RPM Package Manager

For Fedora, the regular file repodata/repomd.xml defines the index: it is a regular file, XML text, the table of contents of the directory. The client fetches it first and reads from it the paths and checksums of the remaining metadata files (Pulp's repository-format reference). Inspecting it is reading text, curl -s <url> | less pages through the file, and each <data> element names one catalog and its checksummed path inside repodata/. The file opens with the primary catalog:

<repomd xmlns="http://linux.duke.edu/metadata/repo">
  <revision>1761190640</revision>
  <data type="primary">
    <checksum type="sha256">fffa3e9f...</checksum>
    <location href="repodata/fffa3e9f...-primary.xml.zst"/>
    <timestamp>1761190628</timestamp>
    <size>16042760</size>
  </data>
  <data type="filelists">
    ...
  </data>
  ...
</repomd>

Among those files, primary.xml is the package catalog, a zstd-compressed XML with one entry per package holding its metadata and dependency data, inspected with zstd -dc primary.xml.zst | less. The entry for the bash package:

<package type="rpm">
  <name>bash</name>
  <arch>x86_64</arch>
  <version epoch="0" ver="5.3.0" rel="2.fc43"/>
  ...
  <location href="Packages/b/bash-5.3.0-2.fc43.x86_64.rpm"/>
  <format>
    ...
    <rpm:requires>
      <rpm:entry name="filesystem" flags="GE" epoch="0" ver="3"/>
      <rpm:entry name="libtinfo.so.6()(64bit)"/>
      <rpm:entry name="rtld(GNU_HASH)"/>
      <rpm:entry name="libc.so.6(GLIBC_2.38)(64bit)"/>
    </rpm:requires>
    <file>/usr/bin/bash</file>
    ...
  </format>
</package>

An RPM dependency can name a file instead of a package: Requires: /usr/bin/sh means whichever package contains that file. Resolving it needs a mapping from files back to their owning packages. The complete mapping is filelists.xml, a second metadata file listing every file of every package, and it is large enough that clients avoid downloading it when possible. As the middle ground, primary.xml embeds a small subset of each package's files, enough to answer the common file dependencies on its own. The subset is a hardcoded rule of createrepo_c, the generator of the repository metadata. A file appears in the subset only when its path is under /etc/ or contains the substring bin/ (plus the one-off /usr/lib/sendmail). The format, however, does not restrict which paths a dependency may name. Requires: /usr/bin/sh is answerable from the catalog alone, while Requires: /usr/share/dict/words is not, and the resolver must fall back to downloading and searching filelists.xml.file

Fedora serves its repositories from dl.fedoraproject.org. The Fedora wiki's Mirroring page documents MirrorManager, "the Fedora Mirror Management system", as keeping track of all the mirrors, and its public page, the mirror list, shows every one of them.

Arch Linux

pacman's index⁴ is the sync database, a tar archive named after the repository it describes, such as core.db and extra.db, refreshed from the mirror when pacman synchronizes. It is a regular file but not plain text: a tar archive holding one directory per package, each with a desc record. Inspecting it is reading the archive, tar -tf core.db lists the package directories, and tar -xOf core.db bash-5.3.15-1/desc prints one record. The first directories in the file:

acl-2.4.0-1/
acl-2.4.0-1/desc
amd-ucode-20260810-2/
amd-ucode-20260810-2/desc
archlinux-keyring-20260727-1/
archlinux-keyring-20260727-1/desc
...

Per alpm-repo-db(7), each directory holds a desc file (alpm-repo-desc(5)) whose format is an all-caps %SECTION% header line followed by its values. The desc entry for the bash package:

%NAME%
bash

%VERSION%
5.3.15-1

%DESC%
The GNU Bourne Again shell
...
%PROVIDES%
sh

%DEPENDS%
readline
libreadline.so=8-64
glibc
ncurses

Arch's entry point is geo.mirror.pkgbuild.com, one of the tier-1 mirrors the project's DevOps team manages. The Arch wiki's Mirrors page names the official sources: the mirror list ships in the pacman-mirrorlist package, the mirrorlist generator offers a more current one, and the mirror status page tracks freshness.

Alpine Linux

Alpine's index⁴ is APKINDEX.tar.gz, one per repository and architecture. It is a regular file, a gzip-compressed tar whose single member APKINDEX is the plain-text index; inspecting it is curl -s <url> | tar -xzO APKINDEX | less. The file opens with the record of the first package, 7zip:

C:Q1Hsn+PTucNsaniz4VLmlaFNKp4nM=
P:7zip
V:24.08-r0
...
D:so:libc.musl-x86_64.so.1 so:libgcc_s.so.1 so:libstdc++.so.6
p:7zip-virtual p7zip=24.08-r0 cmd:7z=24.08-r0 cmd:7zz=24.08-r0

Its records use single-letter fields, each documented in apk-package(5): C: the checksum of the package metadata, P: name, V: version, D: dependencies, p: provides, i: install-if. The entry for the gdk-pixbuf package:

C:Q1piu+yXjbT6J1HCYt1gW/UecNujQ=
P:gdk-pixbuf
V:2.42.12-r1
...
D:shared-mime-info /bin/sh so:libc.musl-x86_64.so.1 so:libglib-2.0.so.0 ...
p:so:libgdk_pixbuf-2.0.so.0=0.4200.12 cmd:gdk-pixbuf-query-loaders=2.42.12-r1 ...

The C: checksum's prefix encodes both representation and algorithm. Per apk-tools' digest parser, the first character selects the encoding (Q for base64, X for hex) and the second the algorithm (1 for SHA-1, 2 for SHA-256). The Q1 prefix seen throughout Alpine's indices is base64-encoded SHA-1, while every other family publishes hex SHA-2 digests.

Alpine's entry point is dl-cdn.alpinelinux.org, the first entry of the mirror list the Alpine wiki's Mirrors page points to; this page also tracks the status of every listed mirror.

Dependency Languages

Packages never stand alone: each one needs, provides, and conflicts with others, and a resolver must read those statements to build a correct closure. This section explores how each of the four families declares them, in its own dependency language, and it covers the grammar of each language and the meaning of each construct.

Debian

SyntaxOperatorsFieldsAlternativesVirtual packagesEssential packages

In the Indices section we have introduced the index for Debian, a remote archive that contains the list of packages available to retrieve. This file defines the relationships between all packages in specific fields, and they use a syntax defined as follows using the EBNF-style notation:

depends     = dependency , dependency , ...        every one must hold
dependency  = alternative | alternative | ...      any one may hold
alternative = package-name [ "(" op version ")" ]
op          = "<<" | "<=" | "=" | ">=" | ">>"

The grammar applies to the relationship fields, and the Fields tab names each field with its meaning. Alternatives covers a dependency that any one of several named packages may satisfy, Virtual packages covers a dependency that any of several packages may satisfy by offering the same shared name, and Essential packages covers the packages a system requires without any declaration naming them.

The operators are intuitive in what meaning they convey:

<< : only versions older than the written one pass.
<= reads "less than or equal": the written version and older pass.
= : only the written version passes.
>= : the written version and newer pass.
>> : only versions newer than the written one pass.

The same syntax serves every relationship field, with one restriction: alternatives may appear only in the fields that declare dependencies, not in Breaks or Conflicts. The fields, defined in Debian Policy 7, each give the declaration its meaning:

Depends and Pre-Depends name packages required for this one to work. Pre-Depends is the stricter form, demanding its packages be fully installed before this one is even unpacked.
Recommends and Suggests name packages that add to this one without being required, in decreasing order of strength.
Breaks and Conflicts name packages that cannot be present together with this one, with Conflicts as the stronger form.

A simple form of declaring a dependency is: Depends: libc6, which is satisfied only by libc6. Some packages can do their job with any one of several interchangeable packages and the syntax lets a dependency express that. A dependency may list several package names separated by pipes, exactly as the grammar's line dependency = alternative | alternative | ... shows, and the pipe reads as "or": the dependency is satisfied when any one of the listed packages is installed. Each listed package is called an alternative.

A package's record can carry a Provides field that lists extra names the package is able to satisfy.

Package: mawk
Version: 1.3.4.20250131-1
Architecture: amd64
Provides: awk
Depends: libc6 (>= 2.38)
Priority: required
Filename: pool/main/m/mawk/mawk_1.3.4.20250131-1_amd64.deb

Each name is a group that several packages may offer, standing for a role rather than for one concrete program, such as awk or mail-transport-agent.

Package: gawk
Version: 1:5.2.1-2+b1
Provides: awk
...

Package: mawk
Version: 1.3.4.20250131-1
Provides: awk
...

Package: original-awk
Version: 2025-01-16-1
Provides: awk
...

Such a group is called a virtual package. A dependency can name it, and the resolver then satisfies the dependency by installing any one of the packages that offer the name, those packages are called its providers.

Essential packages are required without ever being declared. A package marked Essential: yes must be present and functional on every installed system, and other packages are instructed not to declare dependencies on it, since its presence is guaranteed regardless.

Walkthrough: Debian dependencies in FlatRoot

A record's relationship fields reach FlatRoot as text, and the resolver needs a data structure to work with. This walkthrough follows the parsing of that text into FlatRoot's dependency structures. The parsing happens during the index processing walked through in the Indices section: there, catalogue_parse extracts each record from the index text, block_flush closes a completed record, and its call to build assembles the record's fields into a Package, handing each relationship field to depends_parse.

src/package.rs#L162-L180

/// One dependency group: a disjunction of alternatives, any one of
/// which satisfies it.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Dependency {
  /// Disjunctive alternatives in source order — the first
  /// satisfiable entry wins.
  pub alternatives: Vec<DepSpec>,
}

/// One dependency alternative: a package name and an optional version
/// constraint.
#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub struct DepSpec {
  /// Target package name as the source's index reports it.
  pub name: String,
  /// Raw constraint string (such as `">= 2.36"`); absent when
  /// unconstrained.
  pub version_constraint: Option<String>,
}

The parsed form must preserve what the grammar distinguishes: which packages are all required, and which are interchangeable. FlatRoot keeps the distinction in two structures: a Dependency is one comma-separated group, holding its alternatives, any one of which satisfies it, and a DepSpec is one alternative, the package name with its version constraint when one is declared.

src/pkg/deb.rs#L338-L368

fn depends_parse(raw: &str) -> Vec<Dependency> {
  if raw.is_empty() {
    return Vec::new();
  }

  raw
    .split(", ")
    .map(|group| {
      let alternatives = group
        .split(" | ")
        .map(|alt| {
          let alt = alt.trim();
          if let Some(idx) = alt.find(" (") {
            let name = PackageBuilder::arch_qualifier_strip(&alt[..idx]);
            let constraint = alt[idx + 2..].trim_end_matches(')').to_string();
            DepSpec {
              name,
              version_constraint: Some(constraint),
            }
          } else {
            DepSpec {
              name: PackageBuilder::arch_qualifier_strip(alt),
              version_constraint: None,
            }
          }
        })
        .collect();
      Dependency { alternatives }
    })
    .collect()
}

A relationship field mixes both separators, commas between groups and pipes inside them, and the grammar orders them: commas bind the loosest, so they split first. depends_parse follows that order: the field splits at the commas into groups, each group splits at the pipes into its alternatives, and each alternative splits at the opening parenthesis into the package name and the version constraint. Each group becomes one Dependency, holding one DepSpec per alternative.

src/pkg/deb.rs#L372-L397

fn provides_parse(raw: &str) -> Vec<DepSpec> {
  if raw.is_empty() {
    return Vec::new();
  }

  raw
    .split(", ")
    .map(|s| {
      let s = s.trim();
      if let Some(idx) = s.find(" (") {
        let name = s[..idx].trim().to_string();
        let raw = s[idx + 2..].trim_end_matches(')').trim();
        let version = raw.strip_prefix("= ").or(raw.strip_prefix("=")).unwrap_or(raw);
        DepSpec {
          name,
          version_constraint: Some(version.to_string()),
        }
      } else {
        DepSpec {
          name: s.to_string(),
          version_constraint: None,
        }
      }
    })
    .collect()
}

A dependency on a virtual package is only resolvable when the database knows the name's providers, and the Provides field is where a package declares them. The field is a plain list with no alternatives, so provides_parse only splits it at the commas, keeping each name with its pinned version when one is declared. mawk's Provides: awk records it as a provider of awk.

RPM Package Manager

SyntaxOperatorsCapabilitiesRecipesVirtual packagesWeak dependencies

In the Indices section we have introduced primary.xml, the catalog that holds one entry per package. An entry states its relationships in lists, and every item of a list is one <rpm:entry> tag, defined as follows using the EBNF-style notation:

entry      = name [ flags epoch ver [ rel ] ]         one item of a list
name       = capability | "(" expression ")"
capability = package-name | file-path | soname
expression = capability , "and" , capability , ...    every operand must hold
           | capability , "or" , capability , ...     any operand may hold
           | capability , "with" , capability         both, met by one package
           | capability , "without" , capability      the first, not the second
           | capability , "if" , capability [ "else" , capability ]
           | capability , "unless" , capability [ "else" , capability ]
flags      = "LT" | "LE" | "EQ" | "GE" | "GT"

Each operator of the parenthesized form, check boolean dependencies manual for the full reference.

The grammar applies to the lists of an entry, and the Recipes tab names each list with the spec file line it is generated from. Capabilities covers the names packages offer and require and the matching between them, Virtual packages covers a dependency that any of several packages may satisfy by offering the same shared name, and Weak dependencies covers the dependencies an installation may leave unsatisfied.

The flag names, written by createrepo_c, are the five usual comparisons:

LT: only versions older than the written one pass.
LE: the written version and older pass.
EQ: only the written version passes.
GE: the written version and newer pass.
GT: only versions newer than the written one pass.

The version each one compares against is written as [epoch:]version[-release], split into the epoch, ver and rel attributes of the same tag (rpm dependencies manual). For example, <rpm:entry name="filesystem" flags="GE" epoch="0" ver="3"/> asks for the filesystem package at version 3 or newer.

A dependency names a string, and rpm calls that string a capability (rpm-spec(5)). Packages offer capabilities and require them, and a requirement is met when the strings match. The entry for bash in CentOS Stream 9 BaseOS requires filesystem at version 3 or newer and libtinfo.so.6()(64bit), and offers /bin/sh and bash:

<rpm:provides>
  <rpm:entry name="/bin/sh"/>
  <rpm:entry name="bash" flags="EQ" epoch="0" ver="5.1.8" rel="2.el9"/>
  ...
</rpm:provides>
<rpm:requires>
  <rpm:entry name="filesystem" flags="GE" epoch="0" ver="3"/>
  <rpm:entry name="libtinfo.so.6()(64bit)"/>
  ...
</rpm:requires>

To install bash, rpm takes each name in its requires list and looks for a package whose provides list holds the same name. The name filesystem leads to the filesystem package, which offers it at version 3.16:

<rpm:provides>
  <rpm:entry name="filesystem" flags="EQ" epoch="0" ver="3.16" rel="2.el9"/>
  <rpm:entry name="filesystem(x86-64)" flags="EQ" epoch="0" ver="3.16" rel="2.el9"/>
  <rpm:entry name="filesystem-afs" flags="EQ" epoch="0" ver="3.16" rel="2.el9"/>
</rpm:provides>

A dependency can also be conditional using (boolean dependencies):

<rpm:requires>
  <rpm:entry name="(adcli-selinux if selinux-policy-targeted)"/>
  <rpm:entry name="cyrus-sasl-gssapi"/>
  ...
</rpm:requires>

The index is generated from spec files, the recipes maintainers write according to rpm-spec(5). A relationship is one line of a recipe, such as Conflicts: pulseaudio, and it becomes the list of the same name in the package's entry, <rpm:conflicts> (createrepo_c). The pipewire recipe of CentOS Stream 9 declares its PulseAudio implementation as follows:

%package pulseaudio
Summary:        PipeWire PulseAudio implementation
License:        MIT
Recommends:     %{name}%{?_isa} = %{version}-%{release}
Requires:       %{name}-libs%{?_isa} = %{version}-%{release}
Conflicts:      pulseaudio
Supplements:    %{name} = %{version}-%{release}
Obsoletes:      pulseaudio < 14.2-3
Provides:       pulseaudio-daemon
...

Names written %{...} are macros that the build expands, %{name} here to pipewire, and omitted lines are marked .... The meaning of the tags is as follows:

Requires names a capability that has to be present for the package to work, and fills <rpm:requires>.
Provides names a capability the package offers beyond its own name, and fills <rpm:provides>.
Conflicts names a capability that must not be installed alongside the package, and fills <rpm:conflicts>.
Obsoletes names a package this one takes the place of on an update, and fills <rpm:obsoletes>.
Recommends and Suggests name capabilities to install alongside this package, which a resolver may leave unsatisfied, and fill <rpm:recommends> and <rpm:suggests>.
Supplements and Enhances ask the other way around, for this package to be installed alongside the capability they name, and fill <rpm:supplements> and <rpm:enhances>.

The strength of the last four, and the difference between asking and being asked for, is read from an index entry in the Weak dependencies tab.

A dependency can name a virtual package, a capability that several packages offer next to their own names (rpm dependencies manual). The requirement is met by any one of the packages that offer it, so a web application depends on webserver and runs with whichever server the system carries. The entry for nginx in Fedora 43 offers the shared name next to its own:

<rpm:provides>
  <rpm:entry name="nginx" flags="EQ" epoch="2" ver="1.28.0" rel="3.fc43"/>
  <rpm:entry name="webserver"/>
  ...
</rpm:provides>

The entries for httpd, lighttpd and caddy offer webserver as well, and the index holds no package of that name. Learn more in (rpm dependencies manual).

A weak dependency names a package to install alongside this one, and the installation goes through even when the named package cannot be installed (rpm dependencies manual). It is declared in the lists <rpm:recommends>, <rpm:suggests>, <rpm:supplements> and <rpm:enhances>. The entry for firewalld in the Fedora 43 Everything repository declares:

<rpm:recommends>
  <rpm:entry name="ebtables"/>
  <rpm:entry name="ipset"/>
  <rpm:entry name="iptables"/>
</rpm:recommends>
<rpm:suggests>
  <rpm:entry name="iptables-nft"/>
</rpm:suggests>

Installing firewalld also installs the names under <rpm:recommends> whenever they can be installed, while the names under <rpm:suggests> are only offered to the user as options. <rpm:supplements> and <rpm:enhances> state the same relationships in the opposite direction: the package carrying the list is the one to add when the named package is installed.

Arch Linux

SyntaxOperatorsSectionsSonamesOptional dependenciesVirtual packages

In the Indices section we have introduced the sync database, whose desc records group their values under %SECTION% headers. The values of the relationship sections are package relations, and they use a syntax defined as follows using the EBNF-style notation (alpm-package-relation(7)):

relation  = name [ operator version ]       written together, without spaces
optdepend = relation [ ":" description ]
name      = package-name | soname
operator  = "<" | "<=" | "=" | ">=" | ">"

The grammar applies to the relationship sections, and the Sections tab names each section with its meaning. Sonames covers a dependency on a shared library rather than on the package that ships it, Optional dependencies covers a dependency that adds functionality and is left to the user, and Virtual packages covers a dependency that any of several packages may satisfy by providing the same shared name.

The operators are the five usual comparisons (alpm-comparison(7)):

<: only versions older than the written one pass.
<=: the written version and older pass.
=: only the written version passes.
>=: the written version and newer pass.
>: only versions newer than the written one pass.

For example, the glibc>=2.27 of the gcc-libs entry requires glibc at version 2.27 or newer. A comparison whose version omits the packaging release "matches any release of a package version", so =1.0.0 accepts 1.0.0-1 and 1.0.0-2 alike.

A record separates its relations by kind, each kind under a section of its own (alpm-repo-desc(5)). The record for dbus in core declares:

%REPLACES%
libdbus

%CONFLICTS%
libdbus

%PROVIDES%
libdbus
libdbus-1.so=3-64

The meaning of the sections is as follows:

%DEPENDS% holds the run-time dependencies, the relations that must be satisfied for the package to work.
%PROVIDES% holds the names the package provides beyond its own.
%CONFLICTS% holds the names that must not be installed alongside the package.
%REPLACES% holds the names the package "replaces upon installation".
%OPTDEPENDS% holds the optional dependencies of the Optional dependencies tab.
%MAKEDEPENDS% and %CHECKDEPENDS% hold what building the package and running its tests need, rather than installing it.

A relation can name a shared library instead of a package, written as the library's soname with its interface version and word size, so libreadline.so=8-64 is the 64-bit libreadline.so.8 (alpm-sonamev1(7)). The record for bash in core depends on the library next to the package that carries it:

%DEPENDS%
readline
libreadline.so=8-64
glibc
ncurses

and the record for readline provides it:

%PROVIDES%
libhistory.so=8-64
libreadline.so=8-64

Both lines are generated, since a package build tool (e.g. makepkg) automatically derives soname information for ELF files in the build environment: the provision comes from the libraries readline ships, and the dependency from the libraries bash links against.

An optional dependency names a package that "provides optional functionality for a package but is otherwise not required" (alpm-package-relation(7)), and carries the reason to install it after a colon (PKGBUILD(5)). The record for bash in core names its completion scripts:

%OPTDEPENDS%
bash-completion: for tab completion

The shell works without the completions, so the relation requires nothing, and a user who wants them installs the named package.

A relation can name a virtual component, a name that exists because packages provide it rather than because a package is called it (alpm-repo-desc(5)). The record for systemd in core depends on the virtual component dbus-units, and the records for dbus-broker-units and dbus-daemon-units provide it:

%NAME%
dbus-broker-units

%CONFLICTS%
dbus-daemon-units

%PROVIDES%
dbus-units

%NAME%
dbus-daemon-units

%CONFLICTS%
dbus-broker-units

%PROVIDES%
dbus-units

Either provider satisfies the dependency of systemd, and the choice between them belongs to the resolver. The mutual conflict keeps a single provider installed at a time.

Alpine Linux

SyntaxOperatorsFieldsNamespaced providesVirtual packagesInstall-if

In the Indices section we have introduced the APKINDEX record and its single-letter fields. The dependencies in its D: field are constraints, and they use a syntax defined as follows using the EBNF-style notation (apk-world(5)):

dependency = [ "!" ] name [ "@" tag ] [ operator version ]
name       = package-name | file-path | namespaced-name
operator   = "=" | "<" | ">" | ">=" | "~" | ">~" | "<~" | "><"

The ! prefix "changes the dependency constraint to a conflict and ensures that any package matching the specification is not installed", and the @tag suffix allows the package to come from a repository tagged with that name. The record for gettext-dev uses the conflict form, carrying !musl-libintl in its D: field.

The grammar applies to the dependency fields, and the Fields tab names each field with its meaning. Namespaced provides covers the names a build tool generates for the libraries and commands a package ships, Virtual packages covers a dependency that any of several packages may satisfy by providing the same shared name, and Install-if covers a package that installs itself when the packages it names are present.

The operators are the four plain comparisons and the prefix matches (apk-world(5)):

=: only the written version passes.
<: only versions older than the written one pass.
>: only versions newer than the written one pass.
>=: the written version and newer pass.
~ reads "prefix match": every version that starts with the written one passes.
>~: versions newer than or matching the prefix pass.
<~: versions older than or matching the prefix pass.
><: matches an identity hash instead of a version, generated when a package file is added directly.

For example, the python3~3.12 of the pssh record accepts any version of python3 starting with 3.12, the way busybox~1.6 in the man page accepts 1.6, 1.6.0_pre1, and 1.6.9_p1.

A record states each kind of relationship in a field of its own (apk-package(5)). The record for gdk-pixbuf in main declares:

P:gdk-pixbuf
V:2.42.12-r1
D:shared-mime-info /bin/sh so:libc.musl-x86_64.so.1 so:libglib-2.0.so.0 ...
p:so:libgdk_pixbuf-2.0.so.0=0.4200.12 cmd:gdk-pixbuf-query-loaders=2.42.12-r1 ...

The meaning of the fields is as follows:

D: holds the dependencies: "installing this package will require APK to first satisfy the list of all its dependencies".
p: holds the names the package provides "in addition to its primary name and version".
r: holds the packages whose files this one may overwrite, where a file owned by more than one package is otherwise an error.
i: holds the condition under which the package installs itself, read in the Install-if tab.
k: holds the package's priority among the providers of a shared name, read in the Virtual packages tab.

A provided name can carry a namespace prefix, which the format reserves for names a build tool generates (apk-package(5)). abuild, Alpine's package build tool, writes so: for the shared libraries a package ships, cmd: for its commands, and pc: for its pkg-config modules (APKBUILD(5)). The p: field of gdk-pixbuf offers its library and its commands:

p:so:libgdk_pixbuf-2.0.so.0=0.4200.12 cmd:gdk-pixbuf-query-loaders=2.42.12-r1 ...

A dependency names them the same way: the record for pssh carries cmd:ssh in its D: field, asking for the command and staying indifferent to the package that delivers it.

A provided name written without a version is a name several packages may hold at once, which apk considers "a virtual package name" (apk-package(5)). A dependency on it leaves the choice of provider open: either the user names a concrete provider, or the providers carry the provider-priority field k:, which "enables this automatic selection" and determines "which of the packages to install in case multiple packages provide the same non-versioned package name". The records of postgresql16 and postgresql17 in main both provide postgresql and both carry a priority:

P:postgresql16
V:16.15-r0
k:16
p:postgresql cmd:pg_ctl cmd:postgres ...

P:postgresql17
V:17.11-r0
k:17
p:postgresql cmd:pg_ctl cmd:postgres ...

A dependency on postgresql accepts either record, and k: decides between them.

A package can install itself instead of being asked for: "APK will automatically select and install the package if all of the install-if dependencies are satisfied" (apk-package(5)). The record for gdk-pixbuf-doc in main names the docs meta package and its own main package in the i: field:

P:gdk-pixbuf-doc
V:2.42.12-r1
i:docs gdk-pixbuf=2.42.12-r1

The documentation package installs itself exactly when docs and gdk-pixbuf at that version are present, and gdk-pixbuf declares nothing about it. The field must name at least two dependencies, and one of them must carry the = operator.

Versioning

Versions give an order to the packages of a family, and a resolver must reproduce that order when it compares two versions. This section explores how each of the four families encodes and compares versions, covering the syntax of each format and the algorithm behind the comparison.

Debian

SyntaxAlgorithmCharacter walkWalk ExamplesValidation

Per Debian Policy 5.6.12, a version is built from three components:

version          = [ epoch ":" ] upstream-version [ "-" debian-revision ]
epoch            = digit , digit , ...                          an unsigned integer
upstream-version = alphanumeric , { alphanumeric | "." | "+" | "-" | "~" }
debian-revision  = alphanumeric , { alphanumeric | "." | "+" | "~" }

epoch: an integer that overrides every other comparison, 0 when absent. It exists so a package can leave behind a mistaken or incompatible numbering scheme.
upstream-version: the version of the packaged software itself, as published by its authors. It must start with a digit.
debian-revision: counts the Debian packaging changes on top of the same upstream release.

The version string is split at its last hyphen, so hyphens may appear inside the upstream version only when a revision exists to end the string. The record's 5.2.15-2+b10 reads as upstream version 5.2.15 with packaging revision 2+b10 and no epoch.

This algorithm, defined in deb-version(7), is based on the three components:

Compare the epochs as integers. The higher one wins outright: 1:2.0 beats 0:9.9, because the epoch decides before anything after it is read.
If the epochs are equal, compare the upstream versions. If those are equal too, compare the revisions: 5.2.15-2 and 5.2.15-3 tie on the upstream version, and the revisions 2 and 3 decide.
Upstream version and revision are text, compared by the character walk.

This is the character walk behind the third step, an algorithm of its own that works on runs. A run is a maximal stretch of consecutive characters of one kind, digits or non-digits: 5.2.15 breaks into the runs 5, ., 2, ., and 15. The grammar bounds what a run can contain, so a digit run is always a number, and a non-digit run is made of letters and the punctuation . + - ~.

The walk, in pseudocode:

\begin{algorithm}
\caption{Compare two version strings by the character walk}
\begin{algorithmic}
\INPUT  strings $u$ and $v$, with lengths $|u|$ and $|v|$
\OUTPUT $-1$, $0$, or $1$: $u$ is older, equal, or newer than $v$
\STATE $\mathrm{rank}(c)$: $-1$ for the tilde, $0$ for the end of a run, ASCII(c) otherwise
\STATE $i \gets 1$, $j \gets 1$
\WHILE{$i \le |u|$ or $j \le |v|$}
    \COMMENT{one pass per pair of runs}
    \WHILE{$i \le |u|$ and $u[i]$ is not a digit and $j \le |v|$ and $v[j]$ is not a digit}
        \COMMENT{walk the non-digit runs in lockstep}
        \IF{$\mathrm{rank}(u[i]) < \mathrm{rank}(v[j])$}
            \COMMENT{the first differing character decides}
            \RETURN $-1$
        \ELSIF{$\mathrm{rank}(u[i]) > \mathrm{rank}(v[j])$}
            \RETURN $1$
        \ENDIF
        \STATE $i \gets i + 1$, $j \gets j + 1$
    \ENDWHILE
    \IF{$i \le |u|$ and $u[i]$ is not a digit}
        \COMMENT{the first string's non-digit run is longer}
        \RETURN $-1$ if $\mathrm{rank}(u[i]) < 0$, else $1$
    \ENDIF
    \IF{$j \le |v|$ and $v[j]$ is not a digit}
        \COMMENT{the second string's non-digit run is longer}
        \RETURN $1$ if $\mathrm{rank}(v[j]) < 0$, else $-1$
    \ENDIF
    \WHILE{$i \le |u|$ and $u[i]$ is the digit 0}
        \COMMENT{skip the leading zeros of the first digit run}
        \STATE $i \gets i + 1$
    \ENDWHILE
    \WHILE{$j \le |v|$ and $v[j]$ is the digit 0}
        \COMMENT{skip the leading zeros of the second digit run}
        \STATE $j \gets j + 1$
    \ENDWHILE
    \STATE $d \gets 0$
    \WHILE{$i \le |u|$ and $u[i]$ is a digit and $j \le |v|$ and $v[j]$ is a digit}
        \COMMENT{compare the digit runs as numbers}
        \IF{$d = 0$ and $u[i] \ne v[j]$}
            \COMMENT{remember the first differing digit}
            \STATE $d \gets -1$ if $u[i] < v[j]$, else $1$
        \ENDIF
        \STATE $i \gets i + 1$, $j \gets j + 1$
    \ENDWHILE
    \IF{$i \le |u|$ and $u[i]$ is a digit}
        \COMMENT{the longer digit run is the larger number}
        \RETURN $1$
    \ENDIF
    \IF{$j \le |v|$ and $v[j]$ is a digit}
        \COMMENT{the longer digit run is the larger number}
        \RETURN $-1$
    \ENDIF
    \IF{$d \ne 0$}
        \COMMENT{equal length: the first differing digit decides}
        \RETURN $d$
    \ENDIF
\ENDWHILE
\RETURN $0$
\end{algorithmic}
\end{algorithm}

The tilde is the pre-release mechanism, the reason 1.0~beta is older than 1.0 (deb-version(7)).

The pieces assemble into full comparisons. In 5.2.15 against 5.3.1, the leading non-digit runs are empty, the 5 runs tie, the . runs tie, and the digit runs 2 against 3 decide. In 1.1 against 1+b1, the 1 runs tie, and the non-digit runs . against + decide by their ASCII order: 1+b1 is older.

The edge cases all fall out of the same walk. The tilde is the pre-release mechanism: it ranks below the end of a run, so 1.0~beta is older than 1.0.

Non-digit runs that differ are decided by ASCII order: . (46) ranks above + (43), so 1+b1 is older than 1.1.

Leading zeros are skipped before a digit run is compared, so 1.0 and 1.00 are equal.

And when one digit run outlasts the other, the longer run is the larger number: 1.10 is newer than 1.1.

The comparator is directly executable via dpkg --compare-versions:

$ dpkg --compare-versions "1.0~beta" lt "1.0" && echo earlier
earlier

Walkthrough: Debian versions in FlatRoot

The resolver decides between alternatives and checks every constraint by comparing versions, so FlatRoot implements the ordering the specification defines, presented by the Algorithm tabs of the Versioning section. This walkthrough follows how FlatRoot compares two Debian versions. The comparison has two entry points. The resolver checks a candidate against a dependency constraint in candidate_satisfies, reaching the comparator through satisfies. The package database orders the releases of a name with the collation registered in collation_register, reaching it through compare. Both parse their arguments with DebianVersion::parse.

src/version/dpkg.rs#L25-L44

pub(crate) fn parse(version: &str) -> Self {
  let (epoch, rest) = match version.find(':') {
    Some(i) => (version[..i].parse::<u32>().unwrap_or(0), &version[i + 1..]),
    None => (0, version),
  };

  // `rfind` of the last hyphen — upstream segments can themselves
  // contain `-`, so the right-most occurrence is the one that opens
  // the revision tail.
  let (upstream, revision) = match rest.rfind('-') {
    Some(i) => (rest[..i].to_string(), rest[i + 1..].to_string()),
    None => (rest.to_string(), String::new()),
  };

  Self {
    epoch,
    upstream,
    revision,
  }
}

A version arrives as one flat string, while the ordering works on its three components, so the string is split first. parse cuts the epoch at the first colon and defaults it to 0 when the colon is absent. The revision is cut at the last hyphen, the splitting rule of the Syntax tab. Cutting at the last hyphen keeps any earlier hyphen inside the upstream version.

src/version/dpkg.rs#L144-L158

impl Ord for DebianVersion {
  fn cmp(&self, other: &Self) -> Ordering {
    // Epoch dominates absolutely; upstream decides next under the
    // fragment algorithm; revision breaks ties on identical upstreams.
    match self.epoch.cmp(&other.epoch) {
      Ordering::Equal => {}
      ord => return ord,
    }
    match Self::fragment_compare(&self.upstream, &other.upstream) {
      Ordering::Equal => {}
      ord => return ord,
    }
    Self::fragment_compare(&self.revision, &other.revision)
  }
}

With both sides parsed, the components decide in the order of the Algorithm tab: cmp compares the epochs as integers, moves to the upstream versions only on a tie, and to the revisions only on a second tie. The two text components are compared by fragment_compare.

src/version/dpkg.rs#L50-L103

fn fragment_compare(a: &str, b: &str) -> Ordering {
  let a: Vec<char> = a.chars().collect();
  let b: Vec<char> = b.chars().collect();
  let mut ai = 0;
  let mut bi = 0;

  loop {
    // Drain non-digit runs in lockstep, comparing each pair under
    // dpkg's character sort weight. `None` represents "ran out of
    // non-digits" (hit a digit or end-of-string) and is itself a
    // valid sort position via `char_order`.
    loop {
      let ac = if ai < a.len() && !a[ai].is_ascii_digit() {
        Some(a[ai])
      } else {
        None
      };
      let bc = if bi < b.len() && !b[bi].is_ascii_digit() {
        Some(b[bi])
      } else {
        None
      };

      if ac.is_none() && bc.is_none() {
        break;
      }

      match Self::char_order(ac).cmp(&Self::char_order(bc)) {
        Ordering::Equal => {}
        ord => return ord,
      }

      if ac.is_some() {
        ai += 1;
      }
      if bc.is_some() {
        bi += 1;
      }
    }

    if ai >= a.len() && bi >= b.len() {
      return Ordering::Equal;
    }

    // Numeric run — comparison happens as `u64`, not as text, so the
    // shorter run never wins on lexicographic grounds (`9` vs `10`).
    let an = Self::number_extract(&a, &mut ai);
    let bn = Self::number_extract(&b, &mut bi);
    match an.cmp(&bn) {
      Ordering::Equal => {}
      ord => return ord,
    }
  }
}

fragment_compare is the character walk of the pseudocode: the non-digit runs drain in lockstep with each character pair weighed by char_order, and the digit runs that follow are read as whole numbers by number_extract, so 9 loses to 10 on value instead of winning on the first character.

src/version/dpkg.rs#L105-L115

/// dpkg's per-character sort weight: end-of-part at 0, `~` below it,
/// letters at their plain value, every other symbol above the
/// letters, so `1.0a` ranks under `1.0+`.
fn char_order(c: Option<char>) -> i32 {
  match c {
    None => 0,
    Some('~') => -1,
    Some(c) if c.is_ascii_alphabetic() => c as i32,
    Some(c) => c as i32 + 256,
  }
}

The whole ordering of characters lives in one weight. The end of a part weighs 0 and the tilde -1, which is the entire pre-release rule: 1.0~beta runs out of characters below where 1.0 ends. Letters weigh their plain value and every other symbol weighs above the letters, the rule of Debian Policy 5.6.12 that all letters sort earlier than all non-letters.

RPM Package Manager

SyntaxComparisonAlgorithm

Per rpm-version(7), a version is a label of up to three components, known as the EVR:

evr     = [ epoch ":" ] version [ "-" release ]
epoch   = digit , digit , ...                          a non-negative integer
version = alphanumeric , { alphanumeric | "." | "_" | "+" | "~" | "^" }
release = same format as version

epoch: the component that decides before any other, implicitly 0 when omitted. As in Debian, it exists to work around versioning anomalies, and the man page calls it a last resort.
version: the packaged software's own version. The dash cannot appear inside it, since the dash separates the components.
release: the packaging revision within one software version, ideally a plain integer reset to 1 at each new version.

The bash entry's epoch="0" ver="5.2.26" rel="3.fc41" carries the three components already split. Comparison runs left to right across them and stops at the first difference, so a higher epoch wins outright: 5:3.0-1 is newer than 6.0-1. Equal epochs move the decision to the versions, and equal versions to the releases: 1.0-5 is newer than 1.0-1.

Within a component, comparison works on segments rather than characters. Consecutive digits form a numeric segment and consecutive letters an alphabetic one, while the separators only delimit and are never themselves compared: abc123 holds the segments abc and 123 and equals abc.123, and 1.0 equals 1+0. The segments then compare pairwise under four rules, each from the man page:

Numeric segments compare as integers, with leading zeros ignored: abc123 also equals abc.000123.
A numeric segment is always newer than an alphabetic one: 1.0 is newer than 1.xyz.
When one side runs out of segments, the side with more is newer: 0.0 is newer than 0, and 1.xyz is newer than 1.
The operator characters bend the order. A tilde makes its segment sort older, the pre-release mechanism: 2.0~beta1 is older than 2.0 and newer than 1.0. A caret makes it sort newer while staying before the next version: 2.0^150825 is newer than 2.0 but older than 2.0.1.

The segment rules leave two things open, how the text is cut into segments and the order the rules apply in, and both are fixed by rpmvercmp, the comparator inside rpm. The walk cuts and compares one segment pair per pass:

\begin{algorithm}
\caption{Compare two components by rpm's segment walk}
\begin{algorithmic}
\INPUT  strings $u$ and $v$
\OUTPUT $-1$, $0$, or $1$: $u$ is older, equal, or newer than $v$
\WHILE{$u$ or $v$ has characters left}
    \STATE drop the leading separators of $u$ and of $v$
    \COMMENT{every character that is not alphanumeric, a tilde, or a caret}
    \IF{$u$ or $v$ now starts with a tilde}
        \COMMENT{the tilde sorts before everything, the end of the component included}
        \IF{only one side starts with a tilde}
            \RETURN $-1$ if it is $u$, else $1$
        \ENDIF
        \STATE drop the tilde from both sides
        \CONTINUE
    \ENDIF
    \IF{$u$ or $v$ now starts with a caret}
        \COMMENT{the caret sorts after the end of the component, before everything else}
        \IF{one side has ended}
            \RETURN $1$ if it is $v$, else $-1$
        \ENDIF
        \IF{only one side starts with a caret}
            \RETURN $-1$ if it is $u$, else $1$
        \ENDIF
        \STATE drop the caret from both sides
        \CONTINUE
    \ENDIF
    \IF{$u$ or $v$ has ended}
        \BREAK
    \ENDIF
    \STATE $s, t \gets$ the leading segments of $u$ and $v$, cut by the kind of $u$'s first character
    \COMMENT{a digit run when it is a digit, a letter run otherwise}
    \IF{$t$ is empty}
        \RETURN $1$ if $s$ is numeric, else $-1$
        \COMMENT{the sides disagree on the kind: the numeric side is newer}
    \ENDIF
    \IF{$s$ and $t$ are numeric}
        \STATE drop the leading zeros of both
        \IF{their lengths differ}
            \RETURN $1$ if $s$ is longer, else $-1$
            \COMMENT{the longer number is the larger}
        \ENDIF
    \ENDIF
    \IF{$s \ne t$}
        \RETURN their byte order
    \ENDIF
\ENDWHILE
\IF{both sides have ended}
    \RETURN $0$
\ENDIF
\RETURN $-1$ if $u$ has ended, else $1$
\COMMENT{the side with characters left is newer}
\end{algorithmic}
\end{algorithm}

The walk settles the caret example end to end: in 2.0^150825 against 2.0.1, the segments 2 and 0 tie, then the caret meets the digit 1, and since the caret sorts before every character, 2.0^150825 is older.

Arch Linux

SyntaxComparisonAlgorithm

Per vercmp(8), a version has the same three components as RPM's label:

version = [ epoch ":" ] pkgver [ "-" pkgrel ]

epoch: overrules any comparison unless equal on both sides: 2:1.0-1 is newer than 1:3.6-1, and 1:001 is newer than 4.34.
pkgver: the packaged software's own version.
pkgrel: the packaging revision, with one deliberate departure from RPM: it "is only compared if it is available on both versions". Comparing 1.5-1 with 1.5 yields equality, while 1.5-1 against 1.5-2 compares the releases, so a dependency constraint without a release matches every packaging revision of its version.

The component comparison is the segment walk of the RPM Package Manager block, adopted from rpm's rpmvercmp per the attribution in libalpm's source. The man page condenses the behavior into two sorted chains:

Alphanumeric:  1.0a < 1.0b < 1.0beta < 1.0p < 1.0pre < 1.0rc < 1.0 < 1.0.a < 1.0.1
Numeric:       1 < 1.0 < 1.1 < 1.1.1 < 1.2 < 2.0 < 3.0.0

The alphanumeric chain shows the segment rules at work. A letter segment attached to the numbers sorts older than the bare version, so every 1.0x form is a pre-release of 1.0, ordered among themselves by the segment text (a before b before beta). Behind a separator the same letter sorts newer instead: 1.0.a is newer than 1.0, and the numeric segment of 1.0.1 beats the alphabetic a.

The adopted walk is not a verbatim copy, and the departures are what give pacman its own ordering (version.c): the tilde and the caret have no rule of their own and count as ordinary separators, a difference in the number of separators decides before the segments do, and a component that ends while the other continues with letters wins, the rule behind 1.0rc sorting before 1.0 in the chains.

\begin{algorithm}
\caption{Compare two components by pacman's segment walk}
\begin{algorithmic}
\INPUT  strings $u$ and $v$
\OUTPUT $-1$, $0$, or $1$: $u$ is older, equal, or newer than $v$
\WHILE{neither $u$ nor $v$ has ended}
    \STATE drop the leading separators of $u$ and of $v$
    \COMMENT{every character that is not alphanumeric, the tilde and the caret included}
    \IF{$u$ or $v$ has ended}
        \BREAK
    \ENDIF
    \IF{the two sides dropped different numbers of separators}
        \RETURN $-1$ if $u$ dropped fewer, else $1$
    \ENDIF
    \STATE $s, t \gets$ the leading segments of $u$ and $v$, cut as in rpm's walk
    \IF{$t$ is empty}
        \RETURN $1$ if $s$ is numeric, else $-1$
        \COMMENT{the sides disagree on the kind: the numeric side is newer}
    \ENDIF
    \IF{$s$ and $t$ are numeric}
        \STATE drop the leading zeros of both
        \IF{their lengths differ}
            \RETURN $1$ if $s$ is longer, else $-1$
        \ENDIF
    \ENDIF
    \IF{$s \ne t$}
        \RETURN their byte order
    \ENDIF
\ENDWHILE
\IF{both sides have ended}
    \RETURN $0$
\ENDIF
\IF{$u$ has ended}
    \RETURN $1$ if $v$ continues with a letter, else $-1$
    \COMMENT{a leftover of letters reads as a pre-release and loses}
\ENDIF
\RETURN $-1$ if $u$ continues with a letter, else $1$
\end{algorithmic}
\end{algorithm}

The closing rule is the chains' pre-release ordering at work: 1.0rc against 1.0 ties through 1 and 0, then 1.0 ends while 1.0rc continues with letters, and the leftover loses. A numeric leftover still wins, which keeps 1.0.1 newer than 1.0.

Alpine Linux

SyntaxComparisonAlgorithm

apk-package(5) gives the version grammar directly:

version = number { "." number } [ letter ] { "_" suffix [ number ] } [ "~" hash ] [ "-r" number ]

numbers: sequences of digits, forming the dotted core of the version.
letter: a single lowercase letter, allowed only after the last numeric component.
suffixes: words from the fixed set alpha, beta, pre, rc, cvs, svn, git, hg, and p, each optionally followed by a number.
hash: a commit hash of lowercase hexadecimal, recording where the package was built from.
-r number: the package build revision. The entry's 2.42.12-r1 reads as the numeric core 2.42.12 at build revision 1.

Comparison works on the grammar's pieces, each kind ordered by a rule of its own:

The numbers of the dotted core compare as integers. A part with a leading zero instead compares as text, a rule inherited from Gentoo's scheme, so 1.05 is older than 1.1.
The letter compares by its character: 1.0b is newer than 1.0a.
The suffix words rank in the total order alpha < beta < pre < rc < no suffix < cvs < svn < git < hg < p. Words ranked before "no suffix" mark pre-releases and sort older than the bare version, and words ranked after mark snapshots and patches and sort newer: 1.0_rc1 is older than 1.0, and 1.0_p1 is newer.
The suffix numbers and the build revisions compare as integers.

The rules of the pieces still need an order to apply in, and version.c fixes it: apk reads each number of the dotted core, the letter, each suffix with its number, the hash, and the build revision as one piece, called a token, and compares two versions token against token:

\begin{algorithm}
\caption{Compare two versions by apk's token walk}
\begin{algorithmic}
\INPUT  strings $u$ and $v$
\OUTPUT $-1$, $0$, or $1$: $u$ is older, equal, or newer than $v$
\STATE read the first token of each side, the number before the first dot
\WHILE{the two tokens are of the same kind and neither side has ended}
    \IF{the token values differ}
        \RETURN their order
        \COMMENT{numbers as integers, a dotted part with a leading zero as text, letters by character, suffix words by their rank}
    \ENDIF
    \STATE read the next token of each side
\ENDWHILE
\IF{the two tokens are of the same kind}
    \RETURN $0$
    \COMMENT{both sides ended together}
\ENDIF
\IF{$u$'s token is a pre-release suffix}
    \RETURN $-1$
\ENDIF
\IF{$v$'s token is a pre-release suffix}
    \RETURN $1$
\ENDIF
\RETURN $1$ if $u$'s token comes earlier in the grammar, else $-1$
\COMMENT{in particular, the side that ended is older}
\end{algorithmic}
\end{algorithm}

The pre-release check applies the suffix order at the point where the sides diverge: 1.0_rc1 against 1.0 ties on 1 and 0, then 1.0 ends, and since rc ranks before the bare version, the suffix side is older. Every other divergence favors the side that continues, so 1.0_p1 and 1.0.1 are both newer than 1.0.

Resolving the Closure

In this section we explain our approach to resolve the closure, the algorithm is a breadth-first walk over the dependency graph, followed by a fixed-point pass that differs based on the target distribution.

Closure Divergences

Two resolvers can return two different closures for the same request, both valid. The divergences trace back to constructs of the dependency languages.

Virtual packages

A dependency can name a virtual package, a role that several packages offer. On Debian bookworm, the essential package base-files depends on awk, and awk is provided by gawk, mawk, and original-awk. The specification defines who may fill the role and stays silent on who does, so the pick belongs to the resolver, and each pick yields a different graph, every one of them correct:

flowchart LR bf[base-files] -- depends on --> awk{{awk}} awk -. pick .-> g[gawk] awk -. pick .-> m[mawk] awk -. pick .-> o[original-awk]

Hold "Shift" to enable pan & zoom

Walkthrough: virtual packages in FlatRoot

When dealing with virtual packages, the problem is which to select and if it satisfies the constraints to be considered a valid selection. Furthermore, this selection must be deterministic, i.e., the same conditions select the same packages and yield the same package closure. When the walk meets a virtual name, name_resolve resolves it through provider_first, which delegates the pick to one query over the package database.

src/db.rs#L804-L819

/// The one preferred package providing `name`, chosen by priority
/// with ties broken by name so the pick is reproducible; `None` when
/// nothing provides it.
pub fn first(&self, name: &str) -> Result<Option<String>> {
  let mut stmt = self.0.prepare_cached(
    "SELECT p.name
     FROM provides prov
     JOIN packages p ON p.id = prov.package_id
     WHERE prov.name = ?1
     ORDER BY (p.priority IS NULL), p.priority, p.name LIMIT 1",
  )?;
  let mut rows = stmt.query(params![name])?;
  match rows.next()? {
    Some(row) => Ok(Some(row.get(0)?)),
    None => Ok(None),
  }

Several providers may fill the role, so the query needs an order with no ties to make the pick reproducible. first orders the providers by the priority their distribution assigns, the required level ahead of optional, and breaks ties by name. On bookworm, mawk is priority required while gawk and original-awk are optional, so the awk of the divergence example resolves to mawk on every run.

Alternatives

A package may declare its dependencies as several possible choices, called alternatives, as seen in the Alternatives tab of the Dependency Languages section. On bookworm, bsd-mailx declares Depends: default-mta | mail-transport-agent, and any one of the listed alternatives satisfies the group. The order states the packager's preference, and the specification demands nothing beyond one satisfied alternative, so this pick too belongs to the resolver.

Walkthrough: alternatives in FlatRoot

Between the alternatives, only one must be selected. FlatRoot selects by the order the alternatives are written in the dependency line, the preference of the package's author: in default-mta | mail-transport-agent, default-mta is tried first. walk queues each admitted package's dependencies through deps_walk.

src/resolver/walker.rs#L160-L185

fn deps_walk(&mut self, parent: &str, kind: DepKind, silent: bool, queue: &mut VecDeque<String>) -> Result<()> {
  // Dependencies::of returns every comma-separated group on this
  // package's dep line. For `Depends: a | b, c, d | e`:
  //   group 0 = [a, b]   ← `|` means "either is fine"
  //   group 1 = [c]
  //   group 2 = [d, e]
  // The `,` says every group is required, so we walk all of them.
  // The `|` says one alternative per group is enough — dep_resolve
  // picks one and only that one package gets queued. So this loop
  // pushes 3 packages onto the BFS queue here, not 5.
  //
  // How dep_resolve picks: walk the alternatives left-to-right
  // (`a` before `b` — source order is author preference); inside
  // each alt walk its candidates (real package, or every provider
  // of a virtual sorted alphabetically, or the file-path owner for
  // RPM `/path` deps). First candidate whose version satisfies any
  // constraint wins. A version mismatch is never silently accepted
  // — move to the next candidate, then the next alt.
  for dep_group in self.cfg.index.dependencies().of(parent, kind.clone())? {
    if let Some(dep_name) = self.dep_resolve(&dep_group, silent)? {
      self.dep_edge_emit(parent, &dep_group, &dep_name, kind.clone());
      queue.push_back(dep_name);
    }
  }
  Ok(())
}

A dependency line mixes both constructs of the grammar: the commas separate the groups, every one of which must hold, and the pipes separate the alternatives inside a single group, any one of which satisfies it. deps_walk walks every group of the line and queues exactly one package per group, the pick of dep_resolve: the alternatives are tried left to right in their written order, and the first candidate whose version satisfies the constraint wins. Depends: a | b, c, d | e defines three comma-separated groups, where the first and last have two alternatives, so the walk queues three packages, one per group.

File Dependencies

File paths

An RPM dependency can name a file instead of a package: on Fedora 41, gawk requires /usr/bin/sh. The requirement is on whichever package installs that path, so resolving it needs the mapping from files back to their owning packages, published separately from the package index. Several packages may install the same path, so the pick between owners is one more source of divergence.

Walkthrough: file dependencies in FlatRoot

A file path is the last resort of name resolution: a name that is neither a package nor a virtual name may still be a path some package owns. walk reaches this case when it gathers the candidates for a name in candidates_get.

src/resolver/name.rs#L33-L59

/// Every candidate that could satisfy `name`, in preference order:
/// the package itself, else every provider of the virtual name, else
/// the file path's owner.
pub(super) fn candidates_get(&self, name: &str) -> Result<Vec<String>> {
  if self.cfg.index.packages().exists(name)? {
    return Ok(vec![name.to_string()]);
  }
  let providers = self.cfg.index.providers().of(name)?;
  if !providers.is_empty() {
    return Ok(providers.into_iter().map(|p| p.package_name).collect());
  }
  Ok(self.path_owner_get(name)?.into_iter().collect())
}

/// The owner of a dependency spelled as a file path (`/usr/bin/foo`),
/// looked up in the path index when this source publishes one. `None`
/// when the name is not a path, no path index exists, or nothing owns
/// the file.
fn path_owner_get(&self, name: &str) -> Result<Option<String>> {
  if !name.starts_with('/') {
    return Ok(None);
  }
  let Some(index) = self.cfg.index.paths()? else {
    return Ok(None);
  };
  index.query(name)
}

candidates_get tries the three name spaces in preference order: the package itself, then every provider of the virtual name, and last the file path. path_owner_get answers the path case from the path index, the file-to-owner mapping ingested during index processing, and a source that publishes no such mapping resolves no path dependencies.

Version Constraints

Constraint satisfaction

A dependency may accept only some versions of its target: on bookworm, libcrypt1 requires libc6 (>= 2.36). The Versioning section showed the comparison algorithms of each family, and they steer the selection of alternatives and providers: a candidate whose version does not satisfy the constraint is passed over, and the next candidate, then the next alternative, is considered. When the whole list is exhausted, an optional dependency is dropped, while a hard dependency falls back to its first alternative.

Consider that a package bundles several libraries, each with its own version, while other packages depend on those libraries at specific versions. For this case, virtual packages support a mechanism to include a version in the declaration of the Provides: entry: on bookworm, node-acorn declares Provides: node-acorn-bigint (= 1.0.0), node-acorn-node (= 2.0.1), the versions of the libraries it bundles. That way, a constraint on a bundled library is checked against the declared version: node-detective requires node-acorn-node (>= 1.3.0) and node-syntax-error requires node-acorn-node (>= 1.2.0), both pass against 2.0.1, and both packages pull node-acorn.

Walkthrough: version constraints in FlatRoot

Selecting an alternative or a provider is complete only when the candidate's version satisfies the dependency's constraint. The check runs during the selection itself, inside dep_resolve: for each candidate gathered by candidates_get, it calls candidate_satisfies, and the first candidate to pass is the pick.

src/resolver/walker.rs#L244-L260

/// Whether `candidate` satisfies `alt`. An unconstrained alternative
/// is met by any existing package. A constrained one compares against
/// the version `candidate` provides for `alt`'s name when it states
/// one, and against `candidate`'s own version otherwise.
fn candidate_satisfies(&self, alt: &DepSpec, candidate: &str) -> Result<bool> {
  let Some(constraint) = &alt.version_constraint else {
    return self.cfg.index.packages().exists(candidate);
  };
  let version = match self.provides_version_get(&alt.name, candidate)? {
    Some(v) => Some(v),
    None => self.cfg.index.packages().get(candidate)?.map(|p| p.version),
  };
  let Some(version) = version else {
    return Ok(false);
  };
  Ok(self.cfg.index.version_cmp().satisfies(&version, constraint))
}

On bookworm, node-detective requires the acorn-node library at version 1.3.0 or newer: Depends: node-acorn-node (>= 1.3.0). The acorn-node library ships inside another package, node-acorn, and each release of node-acorn bundles a different acorn-node version. To satisfy the constraint, the resolver needs the version of the bundled acorn-node, which is declared in the Provides: version field:

Package: node-acorn
Version: 8.8.1+ds+~cs25.17.7-2
Provides: node-acorn-bigint (= 1.0.0), node-acorn-node (= 2.0.1), ...

As a candidate for node-acorn, its version is 8.8.1+ds+~cs25.17.7-2. As a candidate for node-acorn-node, its version is 2.0.1. The constraint is checked against the version of the name it was written for: 2.0.1 >= 1.3.0, so the check passes. candidate_satisfies takes the version provides_version_get declares for the requested name, else the candidate's own, and compares it with the family's satisfies, the comparators of the Versioning walkthroughs.

Undeclared Requirements

Essential packages and the base

A sane root filesystem contains packages no dependency reaches. Debian marks a set of essential packages, required on every system and deliberately never declared as dependencies, since their presence is guaranteed: bookworm marks 23, bash, coreutils, and dash among them. Every family also assumes a base already present when its package manager runs, the filesystem layout, the C library, a shell. Both must enter the closure by seeding, since no edge of the graph leads to them.

Walkthrough: the seeds' sources in FlatRoot

The seeds are gathered by seed_set, and its two lists come from two different sources.

src/distro/base_packages.rs#L1-L17

//! The base packages a distribution family seeds into every resolve
//! regardless of the request, so a bare install still produces a working
//! base. Families that share a baseline (the RHEL descendants, the
//! pacman descendants) draw it from one place here, so a change is made
//! once; a distribution with its own baseline (openSUSE, Debian, Alpine)
//! keeps it in its own builder.

/// The RHEL-family baseline (CentOS, Fedora, AlmaLinux, Rocky).
pub(crate) const RHEL: &[&str] = &["filesystem", "basesystem", "bash", "coreutils", "glibc", "glibc-common"];

/// The pacman-family baseline (Arch Linux, CachyOS).
pub(crate) const PACMAN: &[&str] = &["filesystem", "glibc", "bash", "coreutils"];

/// One family's base list in the owned form `SourceDistro` carries.
pub(crate) fn from_table(table: &[&str]) -> Vec<String> {
  table.iter().map(|s| s.to_string()).collect()
}

FlatRoot carries two shared lists, one for the RHEL descendants and one for the pacman descendants. openSUSE and Alpine define their own list in their builders, and the Debian family carries an empty one, since the essential set covers its baseline. The base a working system assumes comes from FlatRoot itself. The constants RHEL and PACMAN in the snippet are fixed lists of package names hardcoded in the source, and from_table copies the chosen list into the distribution's description. Every closure includes the baseline of its distribution, independently of the packages the user asked to install.

src/db.rs#L692-L700

/// The packages the distribution designates as always-present, seeding
/// the install set; empty where the distribution has no such notion.
pub fn essential(&self) -> Result<Vec<String>> {
  let mut stmt = self
    .0
    .prepare_cached("SELECT DISTINCT name FROM packages WHERE essential = 1")?;
  let rows = stmt.query_map([], |row| row.get(0))?;
  rows.collect::<Result<Vec<_>, _>>().map_err(Into::into)
}

The essential packages, in contrast, are recorded: the index processing of the Indices section stores each record's Essential: yes mark, and one query returns the whole set at resolve time.

Conditional Dependencies

Boolean dependencies

RPM lets a dependency hold only under a condition on the installed set: on Fedora 41, SDL2 declares (libdecor-0.so.0()(64bit) if libwayland-client), requiring the libdecor library only when libwayland-client is present. The condition reads the final package set, and satisfying it changes that set, so the rule is undecidable while the graph is still being walked: it is evaluated against a complete closure with the fixed-point iteration.

Walkthrough: boolean dependencies in FlatRoot

A conditional dependency is a dependency included only when its condition holds in the closure, so the resolver must evaluate the condition against the closure to decide the inclusion. The expression arrives as text inside the dependency line, and rich_dep_fixpoint needs it as a structure it can evaluate. The work splits in two halves: the parse during package indexing, and the evaluation of one expression during closure resolution.

src/pkg/rpm/richdep.rs#L15-L50

impl RichDepExpr {
  /// Reads a parenthesized rich-dependency formula into the `RichDep`
  /// tree the resolver walks and evaluates.
  pub(super) fn parse(expr: &str) -> Result<RichDep> {
    let inner = expr
      .trim()
      .strip_prefix('(')
      .and_then(|s| s.strip_suffix(')'))
      .unwrap_or(expr.trim())
      .trim();

    if inner.is_empty() {
      bail!("Empty rich dependency expression: '{}'", expr);
    }

    if let Some((left, op, right)) = RichDepExpr::op_split(inner) {
      let left_ast = RichDepExpr::parse(&format!("({})", left))
        .with_context(|| format!("Failed to parse left side of '{}': '{}'", op, left))?;
      let right_ast = RichDepExpr::parse(&format!("({})", right))
        .with_context(|| format!("Failed to parse right side of '{}': '{}'", op, right))?;

      match op {
        "if" => Ok(RichDep::If {
          payload: Box::new(left_ast),
          condition: Box::new(right_ast),
        }),
        "unless" => Ok(RichDep::Unless {
          payload: Box::new(left_ast),
          condition: Box::new(right_ast),
        }),
        "and" => Ok(RichDep::And(Box::new(left_ast), Box::new(right_ast))),
        "or" => Ok(RichDep::Or(Box::new(left_ast), Box::new(right_ast))),
        "with" => Ok(RichDep::With(Box::new(left_ast), Box::new(right_ast))),
        "without" => Ok(RichDep::Without(Box::new(left_ast), Box::new(right_ast))),
        unknown => bail!("Unknown rich dep operator '{}' in: '{}'", unknown, expr),
      }

An expression nests, (A if (B and C)) is legal, so an expression can contain expressions, and the parser must recurse. parse reads the parenthesized text one operator per level, building a tree with one node per operator. The tree is stored in the package database during package indexing, and closure resolution reads it back.

src/resolver/rich_dep.rs#L70-L110

/// Evaluates one rich-dep expression into the packages it calls for
/// given the current set: an `Or` prefers the already-satisfied side,
/// and `If`/`Unless` contribute their payload only when the condition
/// holds.
fn rich_dep_evaluate(&self, dep: &RichDep) -> Result<Vec<String>> {
  match dep {
    RichDep::Pkg(spec) => Ok(vec![spec.name.clone()]),

    RichDep::And(l, r) => {
      let mut result = self.rich_dep_evaluate(l)?;
      result.extend(self.rich_dep_evaluate(r)?);
      Ok(result)
    }

    RichDep::Or(l, r) => {
      let left = self.rich_dep_evaluate(l)?;
      if left
        .iter()
        .try_fold(false, |acc, n| self.is_resolved(n).map(|r| acc || r))?
      {
        Ok(left)
      } else {
        self.rich_dep_evaluate(r)
      }
    }

    RichDep::If { payload, condition } => {
      if self.condition_evaluate(condition)? {
        self.rich_dep_evaluate(payload)
      } else {
        Ok(Vec::new())
      }
    }

    RichDep::Unless { payload, condition } => {
      if !self.condition_evaluate(condition)? {
        self.rich_dep_evaluate(payload)
      } else {
        Ok(Vec::new())
      }
    }

During closure resolution, evaluating the tree answers which packages the expression requires given the current closure, one rule per operator as the snippet shows. Every package an evaluation adds changes the closure, and the changed closure can flip the condition of another expression, so each addition demands a further evaluation round: the rounds repeat until one adds nothing, the fixed point.

Install-if triggers

Alpine allows the opposite: instead of a package in the closure conditionally requiring another, the resolver conditionally includes a package when its triggers are satisfied. On Alpine 3.20, 7zip-doc carries the triggers 7zip and docs, so it is installed once both are in the closure. This rule is also evaluated against the complete closure with the same fixed-point iteration.

Walkthrough: install-if triggers in FlatRoot

Including a triggered package requires two decisions: whether every trigger it names is met by the closure, and whether the package's own dependencies can be satisfied inside it. The install_if_fixpoint function repeats the two decisions until a sweep adds no package.

src/resolver/install_if.rs#L64-L74

/// Whether one trigger is met: the named package is in the closure,
/// or a provider of the virtual name is.
fn trigger_satisfied(&self, trigger: &str) -> Result<bool> {
  let name = Trigger::bare_name(trigger);
  Ok(
    self.state.visited.contains(name)
      || self
        .provider_first(name)?
        .is_some_and(|p| self.state.visited.contains(&p)),
  )
}

The trigger_satisfied function decides whether one trigger is met through a presence test: the test passes when the closure contains the named package, or when it contains a provider of that name, resolved with the same provider logic as every other name.

src/resolver/transitive.rs#L1-L31

//! Adds a triggered package and its full hard-dependency closure as one
//! unit: either the whole closure joins, or the walker state is left
//! exactly as it was.

use std::collections::VecDeque;

use anyhow::Result;

use crate::package::DepKind;

use super::DepWalker;

impl DepWalker<'_> {
  /// Adds a required (rich-dep) package with its full closure; any
  /// unsatisfiable part aborts the whole resolve.
  pub(super) fn transitive_resolve(&mut self, name: &str) -> Result<()> {
    self.transitive_resolve_impl(name, true)?;
    Ok(())
  }

  /// Adds an optional (install-if) candidate with its closure; an
  /// unsatisfiable closure rolls back and returns `false` instead of
  /// failing.
  pub(super) fn transitive_resolve_optional(&mut self, name: &str) -> Result<bool> {
    self.transitive_resolve_impl(name, false)
  }

  /// The shared implementation: adds a package and its whole
  /// hard-dependency chain, rolling back to a pre-walk snapshot when
  /// the chain cannot complete. `strict` decides whether an incomplete
  /// closure is an error or just returns `false`.

An included package brings its own hard dependencies, and including it while one of them cannot be satisfied would leave the closure with an unmet hard dependency. apk skips such a candidate instead of failing the resolution, and FlatRoot matches: the transitive_resolve_optional function adds the candidate together with its full closure as one unit, and any unsatisfiable part rolls the walker back to the exact state before the attempt.

Graph Shape

Cycles

Dependencies form a graph rather than a tree, and the graph carries real cycles: on bookworm, libgcc-s1 depends on libc6 (>= 2.35), and libc6 depends on libgcc-s1. A walk that revisits names never terminates, so every name must be accounted for exactly once.

Walkthrough: cycles in FlatRoot

Termination rests on one invariant, a package is visited at most once during the walk, and the invariant lives in Closure, the walker's state.

src/resolver/walker.rs#L15-L29

/// The state a walk accumulates, kept cheaply clonable so a speculative
/// round can be tried and then kept or discarded whole.
#[derive(Clone, Default)]
pub(super) struct Closure {
  /// Names already accounted for, so a name is never processed twice.
  pub(super) visited: HashSet<String>,
  /// Packages in reach order — because the walk widens one layer at a time,
  /// anything needed by something else comes first, so an install unpacks
  /// strictly in this order (one package's directory before a later one's
  /// files).
  pub(super) order: Vec<String>,
  /// Each "this package drew in that one" link, in the order the choices
  /// were made.
  pub(super) edges: Vec<(String, DepEdge)>,
}

Closure is the walker's memory: visited holds every name already accounted for, and walk skips any name found in it, so libc6 and libgcc-s1 queue each other once.

Install order

The closure's order matters as much as its content, since extraction consumes it package by package. A package that shapes the directory layout must be unpacked before the packages that write into that layout: usrmerge plants the /bin to /usr/bin symlink, and a package extracted into /bin before the symlink exists creates a real directory that breaks the merged layout. The order that satisfies this is dependency-first, every package ahead of the packages that need it.

Walkthrough: install order in FlatRoot

The order is not recomputed at extraction time: the output list of resolve already carries it, and extraction consumes the list as given.

src/commands/install.rs#L374-L385

for pkg in rows_extract {
  let Some(path_file_archive) = downloaded_archive(downloaded, &pkg.name) else {
    continue;
  };
  pb.set_message(format!("extracting {}", pkg.name));
  let identity = PackageIdentity {
    name: pkg.name.clone(),
    arch: arch_uname.to_string(),
  };
  let files = ctx.remote.extract(path_file_archive, &args.root, &identity)?;
  extracted_count += 1;
  pb.inc(1);

The archives_extract function unpacks the archives through one pass over the resolver's list, in its order: a package like usrmerge creates directory symlinks, and a package extracted into /bin before the symlink exists would create a real directory instead. The order itself is the walk's reach order, anything needed by something else ahead of the thing that needs it.

Negative and Optional Relations

Conflicts

Some relations subtract instead of add: on bookworm, postfix conflicts with mail-transport-agent, the very virtual name every mail server provides, so at most one of them may be installed. A conflict constrains the closure without contributing a package to it.

Walkthrough: conflicts in FlatRoot

A conflict must be surfaced without vetoing the install, since the user may have asked for both sides. walk registers each admitted package's conflicts as it admits them.

src/resolver/walker.rs#L262-L292

/// Records `source`'s `Conflicts:`/`Breaks:` entries that apply to
/// the version in the index, so a later conflicting pick prints a
/// warning. A conflict never blocks, since the user may have asked
/// for both packages.
fn conflicts_register(
  &self,
  source: &str,
  kind: DepKind,
  conflict_map: &mut HashMap<String, Vec<String>>,
) -> Result<()> {
  for dep_group in self.cfg.index.dependencies().of(source, kind)? {
    for alt in &dep_group.alternatives {
      let conflict_applies = match &alt.version_constraint {
        Some(constraint) => self
          .cfg
          .index
          .packages()
          .get(&alt.name)?
          .is_some_and(|pkg| self.cfg.index.version_cmp().satisfies(&pkg.version, constraint)),
        None => true,
      };
      if conflict_applies {
        conflict_map
          .entry(alt.name.clone())
          .or_default()
          .push(source.to_string());
      }
    }
  }
  Ok(())
}

conflicts_register records each admitted package's Conflicts and Breaks entries, keeping only the ones whose version constraint matches the version the index carries. The map feeds the check at the top of the walk's loop: a later pick landing on a registered name is reported as a warning, and the resolve continues.

Optional dependencies

Debian's Recommends and Suggests and Arch Linux's optional dependencies mark packages that improve the target without being required, so following them is a choice, and installers choose differently: apt follows Recommends by default (apt.conf(5)), while pacman lists optional dependencies and installs none. Two correct closures for the same target can then differ by every package an optional edge brings in.

Walkthrough: optional dependencies in FlatRoot

Following optional edges is the installer's choice, so the choice must reach the resolver as input. The install command carries it as its --with option, and the resolve reads it from its environment.

src/resolver/env.rs#L1-L18

//! `ResolutionEnv`: the read-only inputs one resolve reads — the
//! package index and the options that widen or narrow the closure.

use crate::db::Index;

/// The read-only inputs one resolve reads.
pub struct ResolutionEnv<'a> {
  /// The package index dependencies are looked up in; it also supplies
  /// the version comparator and the file-to-package data.
  pub index: &'a Index,
  /// Also follow `Recommends:` dependencies, not only hard ones.
  pub include_recommends: bool,
  /// Also follow `Suggests:` dependencies.
  pub include_suggests: bool,
  /// Package names the resolve drops entirely — the named packages and
  /// anything reachable only through them.
  pub exclude: &'a [String],
}

ResolutionEnv is everything one resolve reads, and its two flags are the choice made explicit: include_recommends and include_suggests widen the walk to the optional kinds, both defaulting to off, so the closure FlatRoot builds is the narrow one unless the user asks otherwise. The widening happens where the walk queues dependencies, gated on exactly these flags.

The Graph Walk

The closure's defining question is which packages an installation must contain for the requested ones to work. The resolver answers it with a walk, a breadth-first traversal of the dependency graph. Following declared dependencies gives only part of the answer, since a working system also carries packages nothing declares. Every distribution assumes a base, the filesystem layout, the C library, a shell, and the core utilities, and marks a set of essential packages, required on every installed system and for that reason never declared as dependencies. The walk therefore starts from the seeds: the requested packages, joined with the base and the essential packages. A queue holds the names to visit and a set holds the names already accounted for, so a cycle cannot loop. Each name leaving the queue is resolved to the package that satisfies it: a real package, else the first provider of a virtual name, else the owner of a file path. Every dependency group of that package must hold, so the walk pushes one alternative per group into the queue, the first whose version satisfies the constraint under the family's comparator. A name is accounted for exactly once, so the walk terminates when no new package appears. The names leave the queue in dependency-first order, and that ordered list is the closure, ready for extraction to unpack in sequence.

\begin{algorithm}
\caption{Resolve the dependency closure}
\begin{algorithmic}
\INPUT  the requested packages (e.g. bash)
\OUTPUT the closure in dependency-first order
\STATE S $\gets$ the seeds: requested $\cup$ essential $\cup$ base
\STATE Q $\gets$ a queue holding every seed
\STATE visited $\gets$ the empty set
\STATE order $\gets$ an empty list
\WHILE{Q is not empty}
    \STATE name $\gets$ pop the front of Q
    \IF{name is in visited}
        \STATE continue
    \ENDIF
    \STATE pkg $\gets$ the package satisfying name
    \COMMENT{a real name, a provider of a virtual name, or a path owner}
    \STATE visited $\gets$ visited $\cup$ $\{name\}$
    \FOR{each dependency group of pkg}
        \STATE dep $\gets$ the first alternative whose version satisfies the constraint
        \STATE push dep to Q
    \ENDFOR
    \STATE append name to order
\ENDWHILE
\RETURN order
\end{algorithmic}
\end{algorithm}

Walkthrough: the walk in FlatRoot

FlatRoot runs the walk from the install command down to the ordered closure. The install command resolves the requested patterns into package names and hands them to resolved_set, which builds the seeds and starts the walker through DepWalker::resolve.

src/commands/install.rs#L265-L283

fn seed_set(ctx: &ArchContext, requested: &[String]) -> Result<Vec<String>> {
  let mut seeds: Vec<String> = Vec::new();
  for base in ctx.remote.base_packages() {
    if ctx.index.packages().exists(base)? && !seeds.contains(&base.to_string()) {
      seeds.push(base.to_string());
    }
  }
  for name in ctx.index.packages().essential()? {
    if !seeds.contains(&name) {
      seeds.push(name);
    }
  }
  for p in requested {
    if !seeds.contains(p) {
      seeds.push(p.clone());
    }
  }
  Ok(seeds)
}

The walk needs its starting names before anything else. seed_set gathers them in priority order: the distribution's base packages, kept only when the index carries them, then the essential packages the index reports, then the requested packages, each name entering once.

src/resolver/walker.rs#L103-L109

fn walk(&mut self, requested: &[String]) -> Result<()> {
  let mut queue: VecDeque<String> = VecDeque::new();
  let mut conflict_map: HashMap<String, Vec<String>> = HashMap::new();

  for name in requested {
    queue.push_back(name.clone());
  }

walk realizes the loop of the pseudocode, and it begins with the loop's state: the queue is seeded with the requested names, and a map gathers the conflicts met along the way.

src/resolver/walker.rs#L111-L125

while let Some(name) = queue.pop_front() {
  if self.state.visited.contains(&name) || self.exclude_set.contains(name.as_str()) {
    continue;
  }

  // Resolve the package name (might be a virtual package)
  let real_name = self
    .name_resolve(&name)?
    .ok_or_else(|| anyhow::anyhow!("Package '{}' not found in the index", name))?;

  if self.state.visited.contains(&real_name) || self.exclude_set.contains(real_name.as_str()) {
    continue;
  }

  self.state.visited.insert(real_name.clone());

Each pass of the loop takes one name from the queue. A name already accounted for, or excluded by the user, is skipped. Every other name is resolved to a real package through name_resolve, and the package is marked as accounted for, the guarantee that a cycle cannot loop.

src/resolver/walker.rs#L127-L136

// Check for conflicts with already-selected packages
if let Some(conflictors) = conflict_map.get(&real_name) {
  for c in conflictors {
    eprintln!("  warning: {} conflicts with already-selected {}", real_name, c);
  }
}

// Register this package's Conflicts and Breaks
self.conflicts_register(&real_name, DepKind::Conflicts, &mut conflict_map)?;
self.conflicts_register(&real_name, DepKind::Breaks, &mut conflict_map)?;

A pick can clash with a package already selected. The clash is reported as a warning rather than an error, since the user may have asked for both sides. The package's own Conflicts and Breaks are then registered through conflicts_register, so a later pick that clashes with this one warns too.

src/resolver/walker.rs#L138-L155

    // Queue dependencies (hard).
    self.deps_walk(&real_name, DepKind::Depends, false, &mut queue)?;

    // Queue recommends (silently skip missing — they're optional)
    if self.cfg.include_recommends {
      self.deps_walk(&real_name, DepKind::Recommends, true, &mut queue)?;
    }

    // Queue suggests/optdepends (silently skip missing)
    if self.cfg.include_suggests {
      self.deps_walk(&real_name, DepKind::Suggests, true, &mut queue)?;
    }

    self.state.order.push(real_name);
  }

  Ok(())
}

Every dependency group of the package must hold, so the hard groups are queued through deps_walk, one chosen alternative each. The recommends and suggests kinds are optional, queued only when the install asked for them. The package then joins the order, the closure being assembled.

src/resolver/name.rs#L17-L25

pub(super) fn name_resolve(&self, name: &str) -> Result<Option<String>> {
  if self.cfg.index.packages().exists(name)? {
    return Ok(Some(name.to_string()));
  }
  if let Some(provider) = self.provider_first(name)? {
    return Ok(Some(provider));
  }
  self.path_owner_get(name)
}

A name leaving the queue is not yet a package, since it may name a real package, a virtual name, or a file path. name_resolve tries the three in that order: the real package wins when the index carries the name, else the first provider of the virtual name under a fixed ordering, so the same provider wins every run, else the owner of the file path.

src/resolver/walker.rs#L229-L242

pub(super) fn dep_resolve(&self, dep_group: &Dependency, silent: bool) -> Result<Option<String>> {
  for alt in &dep_group.alternatives {
    for candidate in self.candidates_get(&alt.name)? {
      if self.candidate_satisfies(alt, &candidate)? {
        return Ok(Some(candidate));
      }
    }
  }

  if silent {
    return Ok(None);
  }
  Ok(dep_group.alternatives.first().map(|alt| alt.name.clone()))
}

Each dependency group admits several alternatives, and the walk must pick exactly one. dep_resolve tries the alternatives in the packager's order and, inside each, every candidate able to satisfy it, and the first candidate whose version passes candidate_satisfies wins. A hard group with no fit still returns its first alternative, so the shortfall surfaces at that name instead of disappearing. An optional group with no fit returns nothing.

Fixed Point Iteration

Two constructs from the Dependency Languages section cannot be decided during the walk, because their conditions reference the final closure. RPM's boolean dependencies require (A if B) to add A only when B is already in the set, and Alpine's install-if triggers volunteer a package when every package the trigger names is present. Both are evaluated against the current closure, after the walk, and both can change it, so the evaluation repeats until a pass adds nothing, the fixed point.

\begin{algorithm}
\caption{Apply the conditional rules to a fixed point}
\begin{algorithmic}
\INPUT  the closure from the walk
\REPEAT
    \STATE added $\gets$ false
    \FOR{each conditional rule of a package in the closure}
        \IF{the rule's condition holds in the current closure}
            \STATE add the rule's payload with its own dependencies
            \STATE added $\gets$ true
        \ENDIF
    \ENDFOR
\UNTIL{added is false}
\RETURN the closure
\end{algorithmic}
\end{algorithm}

The two rule sets are the same loop with different conditions. The rich-dependency pass re-evaluates each package's conditional expressions against the current set, adding the payload and its own closure when the condition holds. The install-if pass scans the candidates that carry triggers and admits each one whose triggers are all present, directly or through a provider, skipping a candidate whose own dependencies cannot be satisfied. One admission can satisfy another rule's condition, which is why the loop runs to a fixed point rather than once.

Walkthrough: the fixed point in FlatRoot

The conditional passes run after the walk returns, walk_internal runs the rich-dependency pass and then the install-if pass.

src/resolver/walker.rs#L75-L81

pub(crate) fn walk_internal(cfg: &ResolutionEnv<'_>, requested: &[String]) -> Result<Resolution> {
  let mut walker = DepWalker::new(cfg);
  walker.walk(requested)?;
  walker.rich_dep_fixpoint()?;
  walker.install_if_fixpoint()?;
  Ok(walker.into_resolution())
}

The conditional rules judge their conditions against the closure, so the closure must exist before they run. walk_internal orders the resolve accordingly: the plain dependencies resolve first, then the rich-dependency fixpoint, then the install-if fixpoint.

src/resolver/rich_dep.rs#L17-L31

pub(super) fn rich_dep_fixpoint(&mut self) -> Result<()> {
  loop {
    let mut changed = false;
    let pkgs_with_rich = self.cfg.index.packages().with_rich_deps()?;
    for pkg_name in &pkgs_with_rich {
      if !self.state.visited.contains(pkg_name) {
        continue;
      }
      changed |= self.rich_deps_apply(pkg_name)?;
    }
    if !changed {
      return Ok(());
    }
  }
}

One admission can satisfy the next condition, so a single pass is not enough. rich_dep_fixpoint loops whole passes: each pass re-evaluates the conditionals of every package already in the closure through rich_deps_apply, and the loop ends at the pass that changes nothing, the fixed point.

src/resolver/install_if.rs#L20-L62

pub(super) fn install_if_fixpoint(&mut self) -> Result<()> {
  let mut install_if_skipped: HashSet<String> = HashSet::new();
  loop {
    // Carry the triggers alongside the triggered package so
    // `install_if_edges_record` can attribute the install to every
    // trigger that is present.
    let mut newly_triggered: Vec<(String, Vec<String>)> = Vec::new();

    for (pkg_name, triggers) in self.cfg.index.packages().install_if()? {
      if self.state.visited.contains(&pkg_name) || install_if_skipped.contains(&pkg_name) {
        continue;
      }

      let all_met = triggers
        .iter()
        .try_fold(true, |acc, t| Ok::<_, anyhow::Error>(acc && self.trigger_satisfied(t)?))?;

      if all_met {
        newly_triggered.push((pkg_name, triggers));
      }
    }

    if newly_triggered.is_empty() {
      break;
    }

    // Resolve hard deps of each triggered package — soft semantics: skip
    // triggers whose transitive closure can't be satisfied (matches apk).
    for (trig_name, triggers) in newly_triggered {
      let resolved = self.transitive_resolve_optional(&trig_name)?;
      if !resolved {
        eprintln!(
          "  warning: skipping install-if trigger '{}': transitive hard dep not satisfiable in the current index",
          trig_name,
        );
        install_if_skipped.insert(trig_name);
      } else {
        self.install_if_edges_record(&trig_name, &triggers)?;
      }
    }
  }
  Ok(())
}

An install-if candidate enters the closure through its triggers alone, so the resolver examines the candidates carrying triggers rather than the members of the closure. The install_if_fixpoint function checks every candidate and collects the ones whose triggers are all met, each trigger satisfied by the named package or by one of its providers through trigger_satisfied. An admitted candidate brings its own hard dependencies, and a candidate whose dependencies cannot be satisfied is skipped with a warning and never reconsidered. The examination repeats until it admits nothing, since one admission can meet another candidate's triggers.

Post Extraction Steps

In this section, we present the steps that run after extraction to turn the unpacked tree into a working system. Unpacking leaves every file in place, yet programs also depend on artifacts no package ships: caches derived from the installed files, and configuration that only exists once created on the system itself. We cover the three phases in order, the dynamic-linker cache, the maintainer scripts, and the application caches, closing with where each family runs the caching programs from.

The dynamic-linker cache

An executable finds its shared libraries through the run-time linker, which reads the ordered list written to /etc/ld.so.cache (ldconfig(8)). The cache is built by ldconfig, which scans the installed libraries, creates the soname links, and writes the list. The cache must reflect every library on the tree, so it is built after the last library is unpacked, and because ldconfig may write root-owned files, it "should normally be run by the superuser" (ldconfig(8)), one more place the Background's superuser requirement enters the final steps.

Walkthrough: the dynamic-linker cache in FlatRoot

FlatRoot builds the cache with the superuser requirement removed: ldconfig runs as the unprivileged user, inside namespaces where that user appears as the superuser and the new tree appears as /. This walkthrough follows the cache build from the install command, which runs the post-install phases after the last archive is unpacked.

src/postinstall/plan.rs#L54-L75

pub fn run(&self, post_install: &PostInstall) -> Result<()> {
  if self.phases.is_empty() {
    return Ok(());
  }

  Sandbox::available().map_err(|reason| {
    anyhow::anyhow!(
      "Post-install requires unprivileged user namespaces.\n  \
       {}\n  \
       To enable: sysctl kernel.unprivileged_userns_clone=1\n  \
       To skip post-install: use --postinstall=none",
      reason
    )
  })?;

  // One sandbox session presenting this rootfs at `/`, replayed across
  // every pass below — each `run` call supplies its own command and env.
  let sandbox = Sandbox::new(self.rootfs.path());

  if self.phases.contains(&Phase::Ldconfig) {
    Ldconfig::run(&self.rootfs, &sandbox)?;
  }

The phases need the sandbox before anything runs. run first verifies that unprivileged user namespaces are available, and refuses with the enabling instruction otherwise, since every phase depends on them. One sandbox is then created, presenting the rootfs at /, and the ldconfig phase hands it to Ldconfig::run.

src/postinstall/ldconfig.rs#L18-L37

pub fn run(rootfs: &Rootfs, sandbox: &Sandbox) -> Result<()> {
  let bin = match rootfs.binary_find(&["ldconfig"], None) {
    Some(b) => b,
    None => {
      eprintln!("ldconfig not found, skipping");
      return Ok(());
    }
  };

  let pb = RunVoice::spinner("Running ldconfig");
  let output = sandbox.run(&[&bin], &[])?;

  if output.status.success() {
    RunVoice::finish_ok(&pb, "ldconfig completed");
  } else {
    pb.finish_and_clear();
    eprintln!("ldconfig failed (exit {})", output.status.code().unwrap_or(-1));
  }
  Ok(())
}

The cache must list the libraries of the new tree, not the host's, so the ldconfig that runs is the rootfs's own. Ldconfig::run locates the binary inside the rootfs, and a rootfs without one, the musl families, is skipped rather than failed. The found binary runs through the sandbox, and a failed run is reported rather than aborting the install.

src/sandbox.rs#L160-L189

fn child_run(&self, pipes: ChildPipes, cmd: Vec<String>, env: Vec<(String, String)>) -> ! {
  unsafe {
    libc::dup2(pipes.stdout_write.raw(), 1);
    libc::dup2(pipes.stderr_write.raw(), 2);
  }
  pipes.stdout_write.close();
  pipes.stderr_write.close();
  Fd(0).close();

  if let Err(e) = unshare(CloneFlags::CLONE_NEWUSER | CloneFlags::CLONE_NEWNS) {
    eprintln!("unshare failed: {}", e);
    std::process::exit(126);
  }

  // Signal the parent that unshare is done, then wait for it to write the
  // UID/GID mappings before touching anything identity-dependent.
  unsafe { libc::write(pipes.ready_write.raw(), &0u8 as *const u8 as *const libc::c_void, 1) };
  pipes.ready_write.close();
  let mut buf = [0u8; 1];
  unsafe { libc::read(pipes.maps_read.raw(), buf.as_mut_ptr() as *mut libc::c_void, 1) };
  pipes.maps_read.close();

  if let Err(e) = self.mounts_setup() {
    eprintln!("mount setup failed: {}", e);
    std::process::exit(126);
  }

  Self::environment_replace(&env);
  Self::command_exec(&cmd)
}

ldconfig writes root-owned files under /etc, exactly what an unprivileged user cannot do on a real system. The sandbox removes the obstacle with namespaces: child_run enters a fresh user namespace and mount namespace, waits for the parent to write the UID and GID mappings that turn the unprivileged user into the superuser inside, mounts the rootfs as /, and only then executes the command. To ldconfig, the run is a superuser rebuilding /etc/ld.so.cache on a real root.

The maintainer scripts

Installing a package takes more than placing its files, since some installation steps are commands to run on the target system: bash appends itself to the list of login shells in /etc/shells, and mawk points the shared awk name at itself through update-alternatives. A package ships these steps as its maintainer scripts, executable hooks the package manager runs at install time (Debian Policy 6.1). The scripts expect the finished tree underneath, which is why they run as a post-extraction step: the postinst of bash calls update-alternatives, a program unpacked onto the tree by another package.

Walkthrough: the maintainer scripts in FlatRoot

FlatRoot replays each package's saved install scripts with neither the superuser nor a booted system available. This walkthrough follows the replay from the install command down to one running postinst.

src/commands/install.rs#L116-L121

if total_extracted > 0 {
  let primary_arch = args.archs.first().copied().unwrap_or(Arch::X86_64);
  let remote = RemoteDistro::from_str(&args.remote_str, primary_arch, session.http().clone())?;
  let pi = remote.post_install();
  PostInstallPlan::new(&args.root, &args.postinstall, primary_arch.as_uname()).run(&pi)?;
  Postfix::apply(&args.root)?;

The install command starts the post-install once every archive is extracted, and only when the run changed the rootfs. The distribution was named by the --from argument of the command, and the source identity built from that argument answers post_install, the script behavior to run.

src/distro/kind.rs#L34-L44

/// The post-install behavior this distribution needs; distributions
/// sharing a package format can still differ here.
pub fn post_install(self) -> PostInstall {
  match self {
    Self::Debian | Self::Ubuntu | Self::Centos | Self::Fedora | Self::Alma | Self::Rocky | Self::Opensuse => {
      PostInstall::Debian
    }
    Self::ArchLinux | Self::Cachyos => PostInstall::Arch,
    Self::Alpine => PostInstall::Alpine,
  }
}

Each family names and invokes its script files differently, while one shared loop runs them all, so every distribution maps to one of three behaviors: Debian's, Arch's, and Alpine's. The mapping also shows the RPM families reusing the Debian behavior, which covers their shell scriptlets; a scriptlet written in Lua, the other language RPM allows, is skipped, since the runner interprets only shell. This walkthrough follows the Debian behavior, which replays each postinst the way dpkg would run it.

src/postinstall/plan.rs#L77-L84

// `stubs_install` is the precondition for `scripts_run` — postinst
// scripts shadow privileged commands through the stub PATH, so the
// two are bundled with the `Scripts` phase rather than exposed as a
// separately selectable step.
if self.phases.contains(&Phase::Scripts) {
  post_install.stubs_install(&self.rootfs)?;
  post_install.scripts_run(&self.rootfs, &sandbox, self.arch)?;
}

The chosen behavior lands in the same post-install run the dynamic-linker walkthrough entered. The scripts call commands the bare tree cannot provide, so the phase installs their no-ops before any script runs: stubs_install is the precondition, and scripts_run starts the replay after it.

src/postinstall/debian.rs#L24-L47

pub fn stubs_install(&self, rootfs: &Rootfs) -> Result<()> {
  let stubs = StubSet::new(*rootfs);

  stubs.noop(NOOP_STUBS)?;

  // dpkg stub: handle --compare-versions, no-op everything else
  stubs.script("dpkg", DPKG_STUB)?;

  // update-alternatives stub: create actual symlinks
  stubs.script("update-alternatives", ALTERNATIVES_STUB)?;

  // Stub debconf confmodule — sourced by scripts via `. /usr/share/debconf/confmodule`.
  stubs.seed("usr/share/debconf/confmodule", CONFMODULE_STUB, false)?;
  stubs.seed("usr/share/debconf/frontend", "#!/bin/sh\nexit 0\n", true)?;

  // Create /etc/shells if missing — bash and dash postinst call add-shell which needs it
  stubs.seed_keep("etc/shells", "/bin/sh\n/bin/bash\n/bin/dash\n/usr/bin/bash\n/usr/bin/sh\n")?;

  // add-shell / remove-shell stubs — append to /etc/shells
  stubs.script("add-shell", ADD_SHELL_STUB)?;
  stubs.script("remove-shell", "#!/bin/sh\nexit 0\n")?;

  Ok(())
}

A postinst written for a live system calls the service manager, the user database, and the configuration prompts, none of which exist in a directory tree. stubs_install shadows these commands with no-ops that simply succeed. Some commands are required to really do their work, at least the part that shapes the tree, so FlatRoot implements a minimal working version of each: the update-alternatives stub creates the requested symlinks, the add-shell stub appends to /etc/shells, and the dpkg stub answers the version comparisons the scripts branch on.

src/postinstall/debian.rs#L181-L190

/// An `add-shell` stub that really appends to `/etc/shells` — an
/// unlisted shell is not accepted as a login shell — skipping shells
/// already listed, so repeated runs stay correct.
const ADD_SHELL_STUB: &str = r#"#!/bin/sh
for shell in "$@"; do
    if ! grep -qx "$shell" /etc/shells 2>/dev/null; then
        echo "$shell" >> /etc/shells
    fi
done
"#;

The add-shell stub for example, appends each shell to /etc/shells, skipping the ones already listed. This is the command bash's postinst executes when it registers bash as a login shell.

src/postinstall/debian.rs#L49-L51

pub fn scripts_run(&self, rootfs: &Rootfs, sandbox: &Sandbox, arch: &str) -> Result<()> {
  ScriptReplay::new(*rootfs, sandbox, DebianFlavour, arch).run()
}

With the stubs in place, scripts_run starts the execution, handing it the DebianFlavour: for each package, a Debian install script is a file named postinst with commands to run, and the flavour tells the loop where that file is, the command that runs it, and its environment.

src/postinstall/script.rs#L137-L163

for entry in eligible {
  let dir_name = entry
    .dir
    .file_name()
    .map(|n| n.to_string_lossy().to_string())
    .unwrap_or_default();

  let argv = match self.flavour.stage(&self.rootfs, &entry, &interpreter)? {
    Some(a) => a,
    None => {
      pb.inc(1);
      continue;
    }
  };

  pb.set_message(format!("{} {}", self.flavour.label(), dir_name));

  let env = self.flavour.env(&entry);
  let env_ref: Vec<(&str, &str)> = env.iter().map(|(k, v)| (k.as_str(), v.as_str())).collect();
  let cmd: Vec<&str> = argv.iter().map(|s| s.as_str()).collect();

  let output = self.sandbox.run(&cmd, &env_ref);
  StepReport::print(&pb, self.flavour.label(), &dir_name, &output);

  pb.inc(1);
  self.flavour.cleanup(&self.rootfs);
}

run replays the saved scripts one package at a time. For each saved package, stage copies its postinst into the rootfs and builds the invocation dpkg would use, env supplies the environment the script expects, and the sandbox runs the result with the rootfs as /. A failing script is reported and the replay continues, so one package's breakage never blocks the rest.

src/postinstall/debian.rs#L230-L241

fn env(&self, entry: &ScriptEntry) -> Vec<(String, String)> {
  vec![
    ("PATH".to_string(), "/.flatroot/bin:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin".to_string()),
    ("DPKG_MAINTSCRIPT_NAME".to_string(), "postinst".to_string()),
    ("DPKG_MAINTSCRIPT_PACKAGE".to_string(), entry.identity.name.clone()),
    ("DPKG_MAINTSCRIPT_ARCH".to_string(), entry.identity.arch.clone()),
    ("DPKG_ROOT".to_string(), "".to_string()),
    ("DEBIAN_FRONTEND".to_string(), "noninteractive".to_string()),
    ("HOME".to_string(), "/root".to_string()),
    ("TERM".to_string(), "dumb".to_string()),
  ]
}

The stubs only take effect if the scripts find them first, and the environment arranges it: the PATH that env builds starts at /.flatroot/bin, the stub directory, ahead of the system paths. The remaining variables answer what the scripts branch on: dpkg's own maintainer-script variables, and DEBIAN_FRONTEND=noninteractive, so no script stops at a prompt.

The application caches

An application that needs a font, an icon, or a file-type association cannot afford to scan the whole tree at every start, so caching mechanisms are used: fc-cache builds the font information caches fontconfig reads at startup (fc-cache(1)), update-mime-database builds the Shared MIME-Info cache (update-mime-database(1)), glib-compile-schemas compiles the GSettings schema files into gschemas.compiled (glib-compile-schemas(1)), gtk4-update-icon-cache writes the icon-theme cache (gtk4-update-icon-cache(1)), and update-ca-certificates regenerates the CA trust store from the configured certificate list (update-ca-certificates(8)). Each of these programs reads the files a package installs and writes a compiled cache elsewhere on the tree.

Something must run these programs after extraction places the packages' files, and each family assigns that job to a different place. Debian writes the calls inside the maintainer scripts, an intended use: update-mime-database documents its -n option as existing "for package pre- and post-installation scripts" (update-mime-database(1)). Arch uses separate hook files: a hook names the paths it watches and the command to run, and pacman runs every hook whose watched paths an install changed, after the extraction (alpm-hooks(5)); a hook watching the schema directory runs glib-compile-schemas, and one watching the icon directory runs gtk4-update-icon-cache. Alpine uses trigger scripts, run when an install changes a directory the package watches (apk-package(5)). RPM writes the calls in the scriptlets its packages carry.

Walkthrough: the application caches in FlatRoot

Where the families run the caching programs from their scripts, hooks, and triggers, FlatRoot runs them from one table of its own, as the third phase of the same post-install run the previous two walkthroughs entered. This walkthrough follows the phase from the plan to one rebuilt cache.

src/postinstall/plan.rs#L86-L88

if self.phases.contains(&Phase::Hooks) {
  CacheHooks::run(&self.rootfs, &sandbox)?;
}

The Hooks phase closes the post-install run: it hands the rootfs and the sandbox to CacheHooks::run.

src/postinstall/hooks.rs#L236-L245

pub fn run(rootfs: &Rootfs, sandbox: &Sandbox) -> Result<()> {
  let pb = RunVoice::spinner("Running cache hooks");

  for hook in Self::TABLE {
    hook.resolve_and_run(rootfs, sandbox, &pb)?;
  }

  RunVoice::finish_ok(&pb, "Cache hooks completed");
  Ok(())
}

A fresh rootfs may carry any subset of these programs and the files they summarize, so the rebuild is best-effort by design. run walks a fixed table of every cache FlatRoot knows, in an order where a cache that others read rebuilds first, and one cache's failure never stops the rest.

src/postinstall/hooks.rs#L176-L203

// MIME type database
CacheHook {
  basenames: &["update-mime-database"],
  lib_subdir: None,
  label: "mime-database",
  argv: Argv::Fixed(&["/usr/share/mime"]),
},
// GSettings schemas
CacheHook {
  basenames: &["glib-compile-schemas"],
  lib_subdir: Some("glib-2.0"),
  label: "glib-schemas",
  argv: Argv::Fixed(&["/usr/share/glib-2.0/schemas"]),
},
// GIO modules
CacheHook {
  basenames: GIO_QUERYMODULES,
  lib_subdir: Some("glib-2.0"),
  label: "gio-modules",
  argv: Argv::GioModules,
},
// Icon cache
CacheHook {
  basenames: &["gtk-update-icon-cache"],
  lib_subdir: None,
  label: "icon-cache",
  argv: Argv::IconCache,
},

Each entry of the table is one cache described as data: the candidate names of the program that writes it, the directory to search when that program lives off the PATH, and the command that runs it. The slice shows programs the section introduced: update-mime-database over /usr/share/mime, glib-compile-schemas over the schema directory, and gtk-update-icon-cache, which runs only when the hicolor theme index is present.

src/postinstall/hooks.rs#L111-L133

fn resolve_and_run(&self, rootfs: &Rootfs, sandbox: &Sandbox, pb: &ProgressBar) -> Result<()> {
  let bin = match rootfs.binary_find(self.basenames, self.lib_subdir) {
    Some(b) => b,
    None => return Ok(()),
  };
  let argv = match self.argv.build(rootfs, &bin)? {
    Some(a) => a,
    None => return Ok(()),
  };

  pb.set_message(format!("hook: {}", self.label));

  let env: Vec<(&str, &str)> = vec![
    ("PATH", "/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin"),
    ("HOME", "/root"),
    ("TERM", "dumb"),
  ];

  let cmd: Vec<&str> = argv.iter().map(|s| s.as_str()).collect();
  let output = sandbox.run(&cmd, &env);
  StepReport::print(pb, "hook", self.label, &output);
  Ok(())
}

A cache applies only when the rootfs carries both the program that writes it and the files it summarizes. resolve_and_run locates the program among its candidate names, the multilib -64 and -32 variants included, builds the command, and runs it in the sandbox with the rootfs as /. A missing program or missing input skips the cache, the normal case for a minimal rootfs, and a failed rebuild is reported while the remaining caches still run.

Validation

In this section, we validate the resolution methodology against the package managers themselves. We first state the problem that rules out a plain one-to-one comparison, and define closure sanity, the property the comparison tests instead. Then we present the validation procedure: the experiment applied to every family with its comparison rules, followed by the methodology of each family.

The packaging specifications of the four families define a space of correct solutions rather than a single one, as presented in the Closure Divergences of the Resolving the Closure section: the pick of a provider, the pick of an alternative, and the following of optional dependencies are all choices the specifications leave open. The package manager's installed set is one point in that space, and the resolver's closure is another: awk is satisfiable by mawk and by gawk, so the two can pick differently while both closures stay correct. A plain diff between the two sets reports every such legal difference as an error, failing correct output. The property to test is closure sanity instead, i.e., if the closure is inside the valid solution space. A closure is sane under two conditions. Internally, every hard dependency of every member is satisfied inside the closure itself. Externally, every difference from the package manager's set lies at one of the open choices, and the differing pick satisfies the dependency that the package manager's own pick satisfied.

The Methodology

The experiment produces the two closures that the definition of closure sanity compares. Every family is validated by the same procedure:

Start the distro's official container image.
Inside it, the distribution's package manager installs a target package. The resulting package set is the reference closure.
The resolver proposed in this article resolves the same target against the same repositories. Its output is the computed closure.
Still inside the container, the package manager's metadata is queried recursively, package by package, into the solution space: a graph holding every dependency of every package and every package able to satisfy each, all virtual packages and alternatives included.
The solution space is walked from the same seeds, following the resolver's picks at each open choice. The walk's output is the expected closure, everything the computed closure must contain.
Compare: a package the walk reaches and the computed closure lacks is a missing candidate, and a package only the computed closure holds is a phantom candidate. Each candidate passes through the excusals, the rules that recognize a difference as one of the open choices.
The target passes with zero missing and zero phantom packages.

The missing check and the phantom check split the definition of closure sanity between them. The missing check tests that every hard dependency of every member is satisfied inside the computed closure: a package the walk reaches and the computed closure lacks is an unmet hard dependency. The phantom check tests every package that only the computed closure holds: the package is legitimate when it entered through a choice between alternatives, such as a different provider of the same virtual name.

The Comparison

FlatRoot resolves curl into the computed closure, and apt installs the same curl in Docker into the reference closure. The test then runs apt-cache depends in the container for every package it encounters, recursively, and the answers assemble the solution space. A walk runs over the solution space with the choices of FlatRoot as its reference, starting from curl plus the essential packages. A dependency that a single package can satisfy is followed always. A dependency that several packages can satisfy is followed into the package FlatRoot picked. When FlatRoot picked none of those packages, the walk falls back to the pick of the reference closure, and the missing check then reports that package. When apt also picked none of them, the dependency is skipped, because apt itself left it unsatisfied. Every visited package is collected into the expected closure, the list the computed closure must contain. The missing check judges each package in the expected closure that the computed closure lacks: a candidate absent from the reference closure as well was reached through a branch apt and FlatRoot both skipped, and it is set aside; a candidate whose need the computed closure filled with an alternative, a different provider of the same virtual name, is excused; every other candidate is missing. The phantom check judges each package in the computed closure that the reference closure lacks: a package present in the expected closure is excused; a package that provides a name a member of the reference closure also provides is excused; a package whose own name a member of the reference closure provides is excused, two picks of the same name; every other package is a phantom. The target passes with zero missing and zero phantom packages:

\begin{algorithm}
\caption{Validate the computed closure of one target}
\begin{algorithmic}
\INPUT  a distribution release and a target package $t$
\OUTPUT pass or fail
\STATE $C \gets$ the closure the resolver proposed in this article computes for $t$
\COMMENT{the computed closure}
\STATE $R \gets$ the packages the package manager installs for $t$ in the container
\COMMENT{the reference closure}
\STATE $G \gets$ every dependency and every package able to satisfy each, queried recursively in the container
\COMMENT{the solution space, virtual packages and alternatives included}
\STATE $W \gets \emptyset$, $Q \gets$ a queue holding $t$ and the essential packages
\WHILE{$Q$ is not empty}
    \STATE $p \gets$ pop the front of $Q$
    \IF{$p \in W$}
        \STATE continue
    \ENDIF
    \STATE $W \gets W \cup \{p\}$
    \FOR{each dependency of $p$ in $G$}
        \IF{a single package can satisfy the dependency}
            \STATE push that package to $Q$
        \ELSIF{$C$ holds a package able to satisfy it}
            \STATE push the package $C$ picked to $Q$
            \COMMENT{the walk retraces the resolution of C}
        \ELSIF{$R$ holds a package able to satisfy it}
            \STATE push the package $R$ picked to $Q$
            \COMMENT{C left the dependency unsatisfied; the fallback surfaces the package in the missing check}
        \ELSE
            \STATE skip the dependency
            \COMMENT{R itself left it unsatisfied}
        \ENDIF
    \ENDFOR
\ENDWHILE
\STATE failures $\gets \emptyset$
\FOR{each $p \in W$ with $p \notin C$}
    \COMMENT{W is the expected closure: everything C must contain}
    \IF{$p \notin R$}
        \STATE set $p$ aside
        \COMMENT{the walk reached p through a branch R and C both skipped}
    \ELSIF{a member of $C$ provides the name of $p$, or shares a provided name with $p$}
        \STATE excuse $p$
        \COMMENT{C filled the need with a different provider}
    \ELSE
        \STATE failures $\gets$ failures $\cup \{p\}$
        \COMMENT{p is missing}
    \ENDIF
\ENDFOR
\FOR{each $p \in C$ with $p \notin R$}
    \IF{$p \in W$}
        \STATE excuse $p$
        \COMMENT{the picks of C require p}
    \ELSIF{$p$ provides a name a member of $R$ also provides}
        \STATE excuse $p$
        \COMMENT{the two closures hold different providers of the shared name}
    \ELSIF{a member of $R$ provides the name of $p$}
        \STATE excuse $p$
        \COMMENT{two picks of the same name: C holds the package bearing it, R a provider of it}
    \ELSIF{on Alpine, $p$ carries install-if triggers and every trigger is in $C$}
        \STATE excuse $p$
        \COMMENT{apk itself would include p through its install-if rule}
    \ELSE
        \STATE failures $\gets$ failures $\cup \{p\}$
        \COMMENT{p is a phantom}
    \ENDIF
\ENDFOR
\RETURN pass when failures $= \emptyset$
\end{algorithmic}
\end{algorithm}

Walkthrough: the validation in FlatRoot

The validation procedure runs in FlatRoot's test suite, once per release and target. resolver_debian.rs declares each pair as one test, debian:bookworm with curl among them, and each test hands its pair to validate_deb, the Debian family's entry.

tests/resolver/deb.rs#L16-L33

pub fn validate_deb(remote: &str, image: &str, pkg: &str) {
  let (dep_graph, provides_map, docker_installed, essential_packages) = docker_apt_graph(image, pkg);
  let flatroot = flatroot_resolved_list(remote, pkg);

  let flatroot_set: HashSet<&str> = flatroot.iter().map(|s| s.as_str()).collect();
  let installed_set: HashSet<&str> = docker_installed.iter().map(|s| s.as_str()).collect();

  // Seed BFS with the target package + all Essential packages.
  // This mirrors what FlatRoot does — it resolves from [essentials + user-requested].
  let mut seeds = essential_packages;
  if !seeds.contains(&pkg.to_string()) {
    seeds.push(pkg.to_string());
  }

  let reachable = bfs_reachable(&seeds, &dep_graph, &flatroot_set, &installed_set);

  validate(remote, pkg, &reachable, &docker_installed, &flatroot, &provides_map);
}

The judgments need the algorithm's four sets assembled first, and the validate_deb function gathers them in order. docker_apt_graph starts the container and returns the solution space, the reference closure, and the essential packages. flatroot_resolved_list returns the computed closure. The seeds join the essential packages with the target, bfs_reachable walks the solution space into the expected closure, and validate runs the two checks.

tests/resolver/deb.rs#L52-L65

  let setup_output = container.exec(&format!(
    r#"
export DEBIAN_FRONTEND=noninteractive
apt-get update -qq 2>/dev/null
apt-get install -y -qq {pkg} 2>/dev/null 1>/dev/null

echo '===INSTALLED==='
dpkg -l 2>/dev/null | grep '^ii' | awk '{{print $2}}' | cut -d: -f1 | sort -u

echo '===ESSENTIAL==='
apt-cache dumpavail 2>/dev/null | grep -B10 "^Essential: yes" | grep "^Package:" | sed 's/Package: //' | sort -u
"#,
    pkg = pkg
  ));

The reference closure comes from a real install, so the first container script runs the package manager itself: apt-get install pulls the target, dpkg -l lists every package now on the system, and apt-cache dumpavail lists the packages marked Essential: yes. The installed list is the reference closure, and the essential list seeds the walk the way it seeds the resolver.

tests/resolver/deb.rs#L124-L132

let pkg_list = batch.join(" ");
let script = format!(
  r#"for p in {}; do echo "===PKG:$p==="; apt-cache depends --no-recommends --no-suggests --no-conflicts --no-breaks --no-replaces --no-enhances "$p" 2>/dev/null; done"#,
  pkg_list
);
let output = container.exec(&script);

// Parse output and discover new packages
let (batch_graph, batch_provides, discovered) = parse_apt_batch(&output);

The solution space must hold every branch, while apt-cache depends answers one package at a time, so the discovery runs in rounds. Each round queries one batch of packages, and parse_apt_batch reads the answers into dependency groups, providers, and the names discovered inside them. Every discovered name joins the next round's batch, and the rounds end when a round discovers nothing new.

tests/resolver/mod.rs#L114-L130

pub fn flatroot_resolved_list(remote: &str, pkg: &str) -> Vec<String> {
  let root = TempDir::new().unwrap();
  let cache = TempDir::new().unwrap();
  let output = Command::cargo_bin("flatroot")
    .unwrap()
    .env("FLATROOT_CACHE_HOME", cache.path())
    .args([
      "--from",
      remote,
      "install",
      "--output",
      root.path().to_str().unwrap(),
      "--postinstall=none",
      pkg,
    ])
    .output()
    .expect("flatroot not available");

The computed closure must come out of FlatRoot's real install path, so flatroot_resolved_list runs the flatroot binary: --from names the same release, install resolves and extracts into a temporary directory, and --postinstall=none skips the script replay, since the checks read package names alone. The install writes the manifest .flatroot/packages, and the computed closure is its Package: lines.

tests/resolver/mod.rs#L186-L206

for group in dep_groups {
  if group.len() == 1 {
    // Mandatory dep — follow unconditionally
    queue.push_back(group[0].clone());
  } else if !group.is_empty() {
    // Alternative group — follow the one FlatRoot chose.
    // Check flatroot_set first, then installed_set as fallback
    // (installed_set covers packages that are in the Docker base image
    // which FlatRoot also resolved but through a different name).
    if let Some(chosen) = group.iter().find(|alt| flatroot_set.contains(alt.as_str())) {
      queue.push_back(chosen.clone());
    } else if let Some(chosen) = group.iter().find(|alt| installed_set.contains(alt.as_str())) {
      // Docker chose this alternative, FlatRoot didn't ��� this will be
      // caught as a "missing" package, which is correct.
      queue.push_back(chosen.clone());
    }
    // If no alternative exists in either set, the dep is for something
    // not installed (e.g., a suggests-only package). Skip silently —
    // the missing check will catch it if it matters.
  }
}

The bfs_reachable function retraces FlatRoot's resolution over the solution space through the member it queues for each dependency group. A group with a single member queues that member. A group of alternatives queues the member the computed closure holds, else the member the reference closure holds, so a package FlatRoot skipped still enters the expected closure and meets the missing check. A group with members in neither closure is dropped, since apt itself left it unsatisfied.

tests/resolver/mod.rs#L287-L295

let missing: Vec<&String> = reachable
  .iter()
  // Not in FlatRoot
  .filter(|p| !flatroot_set.contains(p.as_str()))
  // Docker confirms it's genuinely needed (not a BFS artifact)
  .filter(|p| docker_installed.contains(p.as_str()))
  // Not satisfied by an alternative provider in FlatRoot
  .filter(|p| !is_provided_by_flatroot(p, provides_map, &flatroot_set))
  .collect();

The missing check reads as three filters over the expected closure. A candidate outside the computed closure passes the first, and the reference closure holding it passes the second, confirming the genuine need. The third asks is_provided_by_flatroot for a member of the computed closure that provides the candidate's name or shares a provided name with it, the excusal of the algorithm, and a candidate past all three filters is missing.

tests/resolver/mod.rs#L302-L308

let phantoms: Vec<&str> = flatroot
  .iter()
  .filter(|f| !docker_installed.contains(f.as_str()))
  .filter(|f| !reachable.contains(f.as_str()))
  .filter(|f| !is_legitimate_alternative(f, provides_map, docker_installed))
  .map(|f| f.as_str())
  .collect();

The phantom check mirrors the filters from the computed closure's side. A member outside the reference closure and outside the expected closure reaches is_legitimate_alternative, which looks for the provider ties of the algorithm's excusals, and a member with none of them is a phantom.

tests/resolver/mod.rs#L328-L329

assert!(missing.is_empty(), "{} {}: flatroot MISSING {} deps: {:?}", distro, pkg, missing.len(), missing);
assert!(phantoms.is_empty(), "{} {}: flatroot has {} PHANTOM packages: {:?}", distro, pkg, phantoms.len(), phantoms);

The verdict is the pair of asserts: either list holding a survivor fails the test and prints the names, and the target passes with both lists empty.

Appendix

Repositories and package indices

A repository is a plain HTTP server that hosts package archives together with an index, a catalog file listing every available package with its metadata and the path of its archive on the same server. The package manager downloads the index first and works from it alone: dependency resolution and version selection happen locally, and the server is contacted again only to fetch the archives that the resolution selected. Since the whole model runs on static files, any web server or mirror can host a repository. The package formats differ in the index's encoding and location alone: Debian's Packages file sits in the release's dists/ tree (Debian repository format), RPM's XML files sit in a repodata/ directory (repository metadata), pacman's database sits at the repository root (alpm-repo-db(7)), and Alpine's APKINDEX.tar.gz sits per architecture directory (apk-package(5)). The live mirrors expose these layouts as plain directory listings, as seen on Debian bookworm, Fedora 43, Arch core, and Alpine v3.21.

Debian records and RFC 822

RFC 822 is the 1982 standard for the header lines of Internet email, the Key: Value rows at the top of every message. Debian adopted this syntax for its package records, so a record reads like an email, down to the leading-space continuation lines. The Debian Policy Manual makes the compatibility official, citing RFC 5322, the modern revision of RFC 822.

The ar archive format

ar(5) is a Unix archive format that predates tar: it appears in the First Edition Unix manual of 1971, and GNU ar still uses it today to pack compiled object files into static libraries such as libc.a. The format simply concatenates its contents. The archive starts with the magic bytes !<arch>, and each member follows as a fixed 60-byte header with the member's raw content after it. The header is written entirely in printable ASCII, spending 16 bytes on the file name, 12 on the modification time, 6 each on the owner and group, 8 on the permission mode, 10 on the size, and 2 on a closing marker. There is no compression and no index. Debian reuses this container as the outer layer of every .deb file, and the compression lives inside the members instead.

The cpio archive format

cpio(5) is another archive format from early Unix and a close sibling of ar. It is a stream of members, each a small header followed by the file's raw content, without compression or an index of its own. RPM uses the SVR4 variant of the format. Its headers write every numeric field as 8-digit ASCII hexadecimal, which caps individual files at 4 GiB, and the end of the archive is marked by a member called TRAILER!!!.

Checksums and digital signatures

A checksum, also called a hash, is a short value computed from the bytes of a file by a fixed rule. The same file always produces the same checksum, and any change to the file changes it, so comparing checksums reveals whether two files are identical. The rule is chosen so that finding two different files with the same checksum is impractical, which is what makes the comparison trustworthy (GNU Privacy Handbook). A checksum alone does not stop tampering, since an attacker who can replace a file can recompute its checksum too. A digital signature adds that guarantee. The signer keeps a private key and publishes the matching public key. Signing reduces the content to a checksum and encrypts that checksum with the private key, producing the signature, and anyone with the public key can undo the encryption and compare the recovered checksum against one computed from the content itself. Matching checksums mean the content is exactly what the signer signed and has not been altered since, so the signature verifies both who signed it and that it is intact (OpenPGP, signatures over data). A detached signature is stored as its own file or stream next to the signed content rather than inside it, which lets the same content be re-signed by a different key without rewriting it (detached signatures).

The EBNF notation

EBNF, the Extended Backus-Naur Form standardized as ISO/IEC 14977, is a notation for writing grammars. Each rule names a construct and defines what it may contain: sequences list their parts in order, | separates acceptable choices, square brackets surround optional parts, and quoted text stands for characters that appear verbatim. The RFC series uses its own variant of the idea, ABNF.

The ar container is explained in the appendix. ↩
The cpio container is explained in the appendix. ↩
The mechanism behind checksums and digital signatures is explained in the appendix. ↩↩
The publishing model shared by all four formats is explained in the appendix. ↩↩↩
The record syntax's lineage is covered in the appendix. ↩
The EBNF notation is explained in the appendix. ↩

In the Closure of Madness: Spec-based Package Management with Closure-Sanity Validation

Introduction

Background

Archives

Indices

Dependency Languages

Versioning

Resolving the Closure

Closure Divergences

File Dependencies

Version Constraints

Undeclared Requirements

Conditional Dependencies

Graph Shape

Negative and Optional Relations

The Graph Walk

Post Extraction Steps

Validation

The Methodology

The Comparison

Appendix

Repositories and package indices

Debian records and RFC 822

The ar archive format

The cpio archive format

Checksums and digital signatures

The EBNF notation