How to Build a Package Manager — A Complete Implementation Guide

· by 0xKiireguidecpackage managerspackage managertoml

A package manager is one of the most architecturally rich pieces of tooling you can build. It touches dependency resolution (a provably NP-complete problem in the general case), distributed systems (registry protocol, caching), cryptography (integrity verification, signing), filesystem management (content-addressable stores, atomic installs), and UX design (CLI, error messaging). This guide covers every layer, with concrete algorithms and data structures, not hand-waves.

1. Architecture Overview

A package manager decomposes into six distinct subsystems:

CLI
 └─ Resolver          ← version constraint solving
 └─ Fetcher           ← download + integrity verification
 └─ Cache             ← content-addressable store
 └─ Installer         ← atomic filesystem mutations
 └─ Registry Client   ← speaks to package registries

Each is independently testable. The resolver is pure logic — no I/O. The fetcher is I/O-only — no logic. The installer runs last and is the only component that touches the project tree.

2. Package Manifest

The manifest is the source of truth the human author maintains. It declares direct dependencies with version constraints (not pinned versions). Standard fields:

[package]
name    = "my-app"
version = "1.2.3"
license = "MIT"

[dependencies]
http    = "^2.0"
json    = ">=1.4.0, <2.0"
crypto  = "~0.9"

[dev-dependencies]
test-runner = "*"

[build]
script  = "build.sh"
targets = ["linux-x86_64", "darwin-arm64", "windows-x86_64"]

Version Constraint Syntax (SemVer)

Syntax Meaning
1.2.3 Exactly 1.2.3
^1.2.3 >=1.2.3, <2.0.0 — minor/patch can move
~1.2.3 >=1.2.3, <1.3.0 — patch can move only
>=1.0, <2 Explicit range
* Any version
1.2.x >=1.2.0, <1.3.0

Internally, parse every constraint into a VersionReq:

typedef struct {
    enum { GTE, GT, LTE, LT, EQ } op;
    SemVer version;
} VersionReq;

typedef struct {
    VersionReq *reqs;  // AND-ed together
    size_t      count;
} VersionConstraint;

^2.0 → [GTE 2.0.0, LT 3.0.0]
~1.4.2 → [GTE 1.4.2, LT 1.5.0]

3. The Lockfile

The lockfile is machine-generated and pins every package in the full transitive closure to an exact version + content hash. It is committed to source control and guarantees reproducible installs across machines.

# lockfile.lock — generated, do not edit

[[package]]
name     = "http"
version  = "2.3.1"
source   = "registry+https://packages.example.com"
checksum = "sha256:e3b0c44298fc1c149afbf4c8996fb924..."

  [[package.dependencies]]
  name    = "tcp"
  version = "1.0.4"

[[package]]
name     = "tcp"
version  = "1.0.4"
source   = "registry+https://packages.example.com"
checksum = "sha256:a87ff679a2f3e71d9181a67b7542122c..."

The lockfile must be:

  • A complete, flat list of every package at a pinned version
  • Reproducibly regeneratable from the manifest alone
  • Human-readable enough to review in diffs

4. Registry Design

The registry is a content server that the package manager client queries. Two models exist:

4.1 Centralized Registry (npm, crates.io model)

One canonical server hosts all packages. Clients always know where to look.

API surface (minimal HTTP REST):

GET  /packages/{name}              → package metadata (all versions)
GET  /packages/{name}/{version}    → specific version metadata
GET  /packages/{name}/{version}.tar.gz → source tarball
POST /packages/publish             → upload a new package (auth required)
GET  /packages?q={query}&limit=20  → search

Package metadata response:

{
  "name": "http",
  "versions": {
    "2.3.1": {
      "checksum": "sha256:e3b0c44...",
      "dependencies": {
        "tcp": "^1.0"
      },
      "yanked": false,
      "published_at": "2025-01-15T10:00:00Z"
    }
  },
  "latest": "2.3.1"
}

The client should cache the metadata aggressively. Index files (like crates.io's git index) let you download the entire dependency graph metadata without one HTTP round-trip per package.

4.2 Index Design — Avoid N+1 Round Trips

For a cold install with 200 transitive deps, you cannot afford 200 sequential HTTP requests. Solutions:

Git-based sparse index (crates.io model): A git repo where each file corresponds to a package name. The client does a shallow clone and reads files locally. Dependency resolution works entirely offline once the index is cloned.

Bulk metadata fetch: Package manager sends a POST with {"packages": ["http", "tcp", "json", ...]} and gets back all metadata in one response. Solves the first-install case.

Prefetch heuristic: After resolving, queue all tarball downloads in parallel before any install begins.

4.3 Running Your Own Registry

A minimal registry is just:

  1. A blob store (S3-compatible or local filesystem)
  2. A metadata database (Postgres, SQLite)
  3. An HTTP server that reads from both
/store/{sha256-hash}       → raw tarballs, content-addressed
/meta/{name}.json          → package metadata, mutable

Separation of the blob store and metadata store lets you put tarballs on a CDN while keeping metadata fast to query.

5. Dependency Resolution — The Hard Part

Dependency resolution is the core algorithm of any package manager. Given a manifest with direct dependency constraints, find a set of packages + exact versions that satisfies all constraints transitively, or report why one doesn't exist.

5.1 Naive DFS (Works for Small Graphs)

typedef struct {
    char *name;
    SemVer version;
} Selection;

bool resolve(
    const char *pkg,
    VersionConstraint constraint,
    HashMap *selected,   // name → SemVer (already chosen)
    Vec *result          // output flat list
) {
    SemVer *already = hashmap_get(selected, pkg);
    if (already) {
        return satisfies(constraint, *already);  // conflict if not
    }

    Vec candidates = registry_versions(pkg);  // newest first
    for (size_t i = 0; i < candidates.len; i++) {
        SemVer v = candidates.data[i];
        if (!satisfies(constraint, v)) continue;

        // Try selecting this version
        hashmap_set(selected, pkg, v);

        Manifest m = registry_metadata(pkg, v);
        bool ok = true;
        for (size_t j = 0; j < m.deps.len; j++) {
            if (!resolve(m.deps[j].name, m.deps[j].constraint, selected, result)) {
                ok = false;
                break;
            }
        }

        if (ok) {
            vec_push(result, (Selection){pkg, v});
            return true;
        }

        // Backtrack
        hashmap_remove(selected, pkg);
    }

    return false;  // no version works
}

This is backtracking search — exponential in the worst case. Real package managers need better.

5.2 PubGrub — The Modern Algorithm

PubGrub (used by Dart's pub, Rust's cargo fork) is a DPLL-inspired algorithm that produces human-readable error messages and is efficient in practice. Key ideas:

Terminology:

  • Incompatibility: A clause saying "these packages at these versions cannot all be selected simultaneously." (Like a DPLL clause.)
  • Term: (package, constraint) — either positive ("must satisfy") or negative ("must not satisfy")
  • Assignment: A partial solution built incrementally

Algorithm sketch:

Initialize with root package as a unit clause.
Loop:
    unit_propagate()          // derive forced assignments from known incompatibilities
    if conflict → backtrack and learn a new incompatibility clause
    if complete → done
    pick_next_package()       // heuristic: pick most-constrained
    add_new_incompatibilities_for(chosen_package)

The key property: when a conflict is found, PubGrub derives a new incompatibility that captures exactly why the conflict occurred, not just which package caused it. This means:

  1. Error messages say "package A requires X>=2 but package B requires X<2" rather than "conflict"
  2. Learned clauses prune the search space, making subsequent iterations faster

Implementation note: PubGrub operates on version ranges, not individual versions. A term like (http, ^2.0) means "http must be in [2.0.0, 3.0.0)". The algorithm manipulates these ranges algebraically without enumerating individual versions.

The full PubGrub spec: https://github.com/pubgrub-rs/pubgrub

5.3 Minimum Version Selection (Go model)

Go's module system uses a deliberately simpler algorithm: always select the minimum version that satisfies all constraints. No backtracking. O(n) in the number of packages.

This works because Go uses require directives that specify exact minimum versions needed. The algorithm is:

For each direct dependency:
    v = max(explicitly required version, minimum needed by any transitive dep)

The tradeoff: deterministic and fast, but may select older versions than ^ semantics would want, so packages must be careful about compatibility.

5.4 SAT Solver Approach (npm v3+)

For the general case, encode the problem as a boolean satisfiability instance:

  • Variable for each (package, version) pair
  • Clause: "at least one version of package X must be selected"
  • Clause: "at most one version of package X may be selected"
  • Clause: "if (http, 2.3.1) is selected, then (tcp, 1.0.4) must be selected"

Feed to a SAT solver (MiniSAT, CaDiCaL). This is complete but slow for very large graphs. In practice, PubGrub is preferred for package managers.

6. Content-Addressable Storage (CAS)

The cache should be a content-addressable store: packages are stored and retrieved by their content hash, not their name or version. This has several properties:

  1. Deduplication is automatic — two packages sharing a dependency at the same version share the same files on disk
  2. Verification is implicit — if the hash matches, the content is correct
  3. Cache invalidation is trivial — cached content is immutable

6.1 Filesystem Layout

~/.cache/pkgman/
  cas/
    blobs/
      e3/b0c44298fc1c149afb...  ← raw tarballs, named by sha256
      a8/7ff679a2f3e71d9181...
    tmp/                         ← in-progress downloads land here first
  index/
    registry.example.com/
      http/
        2.3.1.json               ← cached metadata
      tcp/
        1.0.4.json
  packages/                      ← extracted package trees
    http/2.3.1/                  ← extracted from blob
    tcp/1.0.4/

6.2 Download + Verify Pipeline

typedef struct {
    char sha256[65];   // expected hash from lockfile
    char url[512];
    char dest[512];    // path in CAS blobs/
} DownloadTask;

int download_and_verify(DownloadTask task) {
    // 1. Check if blob already exists in CAS
    if (file_exists(task.dest)) {
        if (verify_sha256(task.dest, task.sha256)) return 0;  // cache hit
        unlink(task.dest);  // corrupted — re-download
    }

    // 2. Download to temp file
    char tmppath[512];
    snprintf(tmppath, sizeof(tmppath), "%s/tmp/%s.partial", CACHE_DIR, task.sha256);
    
    FILE *tmp = fopen(tmppath, "wb");
    SHA256_CTX ctx;
    SHA256_Init(&ctx);

    http_download(task.url, tmp, &ctx);   // stream, hashing on the fly
    fclose(tmp);

    // 3. Verify
    char actual[65];
    SHA256_Final_Hex(&ctx, actual);
    if (strcmp(actual, task.sha256) != 0) {
        unlink(tmppath);
        return EINTEGRITY;
    }

    // 4. Atomic move into CAS (rename is atomic on POSIX)
    rename(tmppath, task.dest);
    return 0;
}

Never write partially-downloaded files into the CAS. Always download to a temp path in the same filesystem, verify, then atomically rename.

6.3 Parallel Downloads

Queue all downloads before starting any. Use a thread pool or async I/O:

ThreadPool pool = threadpool_create(8);  // 8 concurrent downloads

for (size_t i = 0; i < downloads.len; i++) {
    threadpool_submit(&pool, download_and_verify, downloads.data[i]);
}

threadpool_wait(&pool);  // all downloads complete before extraction begins

With parallel downloads, a 200-package install that would take 40 seconds serially takes 5-8 seconds.

7. Installation — Linking Strategies

After downloading, packages need to appear in the project. Three strategies:

7.1 Copy

Simple: copy the extracted package tree into ./packages/{name}/{version}/. Safe, portable, but uses more disk space.

Hardlink files from the CAS into the project tree. Zero-copy, near-instant. Works when the CAS and project are on the same filesystem (almost always true for local development).

// For each file in the extracted package:
link(cas_path, project_path);  // POSIX hardlink — no data copied

If the CAS is on a different filesystem (network mounts, Docker volumes), fall back to copy.

Symlink entire package directories. Simplest, but causes issues with packages that do relative path traversal or use __dirname (Node.js-specific problem).

7.4 Virtual Store + Single Flat Directory (pnpm model)

Keep a single flat CAS. Expose packages to the project via a .packages virtual store with precise symlinks. Avoids the diamond dependency problem in node_modules by ensuring each package only ever has its resolved dependency tree, not a flattened merge.

.packages/
  http@2.3.1/              ← symlinks to CAS
    node_modules/
      tcp → ../tcp@1.0.4   ← precise dependency symlink
  tcp@1.0.4/

7.5 Atomic Installation

Never leave a project in a partially-installed state. Use a two-phase approach:

  1. Phase 1: Download everything, verify everything, extract everything to a temp staging directory
  2. Phase 2: Atomically rename the staging directory to the final location, or apply hardlinks in a single pass

If the process is killed mid-install, Phase 1 leaves only temp files (easily cleaned up). Phase 2 either completes or doesn't begin.

8. CLI Design

The CLI is what most users interact with. Commands:

pkgman init                     # scaffold manifest
pkgman add <pkg>[@version]      # add dependency, resolve, update lockfile
pkgman remove <pkg>             # remove dependency
pkgman install                  # install from lockfile (CI-safe)
pkgman update [pkg]             # update to latest satisfying version
pkgman upgrade [pkg]            # upgrade past major versions (asks)
pkgman build                    # invoke build script
pkgman run <script>             # run named script from manifest
pkgman publish                  # publish to registry
pkgman search <query>           # search registry
pkgman info <pkg>               # show package metadata
pkgman audit                    # check for known vulnerabilities
pkgman cache clean              # purge CAS
pkgman why <pkg>                # explain why a package is in the tree

8.1 add vs install

This distinction matters:

  • add: Modifies the manifest, re-resolves, rewrites the lockfile, installs
  • install: Reads the existing lockfile exactly, installs what's pinned — no resolution

install must be deterministic and never touch the manifest or lockfile. CI pipelines always use install.

8.2 Progress Output

During a large install, users need feedback. A minimal but effective progress display:

Resolving dependencies...  142 packages
Downloading              ████████████░░░░░░░░  64/142
  tcp@1.0.4              ████████████████████  done
  http@2.3.1             ████████░░░░░░░░░░░░  42%
Installing               waiting...

Implement with terminal ANSI escape codes. Write progress to stderr, not stdout, so piping output still works.

8.3 Error Messages

The bar for package manager error messages is high. Compare:

Bad:

Error: version conflict

Good (PubGrub-style):

error: dependency conflict

  my-app requires:
    http ^2.0
    grpc ^1.0

  grpc@1.4.2 requires:
    http ^1.5

  Because http ^2.0 is incompatible with http ^1.5,
  grpc@1.4.2 cannot be selected.

  Try: pkgman add grpc@2.0 (which lifted the http requirement)
  Or:  downgrade http to ^1.x

The resolver must carry provenance — which package requested which version — to generate this output.

9. Security Model

9.1 Integrity Verification

Every lockfile entry carries a content hash. Verify on every install, even from cache:

bool verify_package(const char *path, const char *expected_sha256) {
    uint8_t hash[32];
    sha256_file(path, hash);

    char hex[65];
    bytes_to_hex(hash, 32, hex);
    return strcmp(hex, expected_sha256) == 0;
}

Use SHA-256 at minimum. For extra security, store both SHA-256 and BLAKE3 (faster to compute).

9.2 Package Signing

Signing prevents a compromised registry from serving modified packages.

Model 1: Registry-signed (GPG detached signatures)

Registry signs each tarball with its private key. Clients verify against the known public key baked into the package manager binary.

GET /packages/http/2.3.1.tar.gz      → tarball
GET /packages/http/2.3.1.tar.gz.sig  → detached signature

Model 2: Transparency Log (Sigstore model)

Every publish event is recorded in an append-only, publicly auditable log (like Certificate Transparency for TLS). Clients check that the package version appears in the log before trusting it. Tampered packages without a log entry are rejected.

This is the modern standard and significantly harder to attack than pure registry signing.

9.3 Namespace Squatting and Typosquatting

Mitigations:

  • Require human verification (email, 2FA) before first publish
  • Flag packages with names similar to top-100 popular packages during upload
  • Allow package owners to reserve namespace prefixes (e.g., my-org/*)
  • Show download counts prominently — typosquatted packages have zero

9.4 Audit / Vulnerability Database

Maintain or consume a vulnerability database keyed by (package, version_range):

{
  "package": "http",
  "advisory": "PKGSA-2025-0042",
  "severity": "high",
  "affected": ">=2.0.0, <2.3.1",
  "patched_in": "2.3.1",
  "description": "HTTP request smuggling via chunked encoding"
}

pkgman audit reads the lockfile, checks every pinned version against the database, and reports vulnerable packages with remediation paths.

10. Workspace / Monorepo Support

Modern projects are often monorepos. A workspace is a root manifest that references multiple packages:

# workspace root
[workspace]
members = [
  "packages/core",
  "packages/cli",
  "packages/server",
]

The resolver treats all workspace members as a single resolution unit — they share a single lockfile. Cross-member dependencies are resolved locally (source, not registry), with registry fallback.

Workspace resolution order:
1. Can this dep be satisfied by a workspace member? → use local source
2. Else → use registry

This means packages/cli can declare core = "^1.0" and get the local workspace packages/core during development, but publish as a normal registry dep for external consumers.

11. Build System Integration

The package manager installs packages, but it must also help the build system find them.

11.1 Generated Build Files

After install, emit a build-system-specific file that maps package names to filesystem paths:

For a C/C++ project (CMake):

# generated by pkgman — do not edit
set(HTTP_INCLUDE_DIR "/home/user/.cache/pkgman/packages/http/2.3.1/include")
set(HTTP_LIB_DIR     "/home/user/.cache/pkgman/packages/http/2.3.1/lib")
target_link_libraries(my_app PRIVATE ${HTTP_LIBRARIES})

For Zig (0.16.0 build.zig.zon):

// generated by pkgman
.dependencies = .{
    .http = .{
        .url  = "file:///home/user/.cache/pkgman/packages/http/2.3.1.tar.gz",
        .hash = "122068...",
    },
},

11.2 Environment-Based Discovery

Alternatively, set environment variables before invoking the build:

export PKG_HTTP_INCLUDE=/home/user/.cache/pkgman/packages/http/2.3.1/include
export PKG_HTTP_LIB=/home/user/.cache/pkgman/packages/http/2.3.1/lib
export PKG_TCP_INCLUDE=...

Build scripts read these. Portable but leaks global state.

11.3 Shims and PATH

For binary tools distributed as packages (linters, formatters), install shims into a project-local .bin/ directory and prepend it to PATH in shell integrations.

12. Implementing the Version Parser

SemVer parsing is the first concrete thing to write. It's small enough to be testable in an afternoon.

typedef struct {
    uint32_t major, minor, patch;
    char     pre[64];   // pre-release: "alpha.1", "rc.2"
    char     build[64]; // build metadata (ignored in comparisons)
} SemVer;

// Returns 0 on success, -1 on parse error
int semver_parse(const char *s, SemVer *out) {
    memset(out, 0, sizeof(*out));
    int n = sscanf(s, "%u.%u.%u", &out->major, &out->minor, &out->patch);
    if (n < 1) return -1;

    const char *pre = strchr(s, '-');
    if (pre) strncpy(out->pre, pre + 1, sizeof(out->pre) - 1);

    return 0;
}

// Returns -1, 0, 1 (like strcmp)
int semver_cmp(SemVer a, SemVer b) {
    if (a.major != b.major) return a.major < b.major ? -1 : 1;
    if (a.minor != b.minor) return a.minor < b.minor ? -1 : 1;
    if (a.patch != b.patch) return a.patch < b.patch ? -1 : 1;
    // Pre-release: version with pre-release < version without
    if (*a.pre && !*b.pre) return -1;
    if (!*a.pre && *b.pre) return 1;
    return strcmp(a.pre, b.pre);
}

bool semver_satisfies(SemVer v, VersionConstraint c) {
    for (size_t i = 0; i < c.count; i++) {
        int cmp = semver_cmp(v, c.reqs[i].version);
        bool ok;
        switch (c.reqs[i].op) {
            case GTE: ok = cmp >= 0; break;
            case GT:  ok = cmp >  0; break;
            case LTE: ok = cmp <= 0; break;
            case LT:  ok = cmp <  0; break;
            case EQ:  ok = cmp == 0; break;
        }
        if (!ok) return false;
    }
    return true;
}

13. Lockfile Generation and Parsing

The lockfile writer runs after resolution and must be deterministic — same inputs always produce byte-identical output. This means:

  • Sort packages by name, then version
  • Sort dependency lists within each package
  • Use fixed-precision for all numeric values
  • Never include timestamps or non-deterministic data
void lockfile_write(FILE *f, ResolvedPackage *pkgs, size_t count) {
    // Sort for determinism
    qsort(pkgs, count, sizeof(*pkgs), compare_package_name_version);

    fprintf(f, "# Generated by pkgman %s — do not edit\n\n", VERSION);

    for (size_t i = 0; i < count; i++) {
        ResolvedPackage *p = &pkgs[i];
        fprintf(f, "[[package]]\n");
        fprintf(f, "name     = \"%s\"\n", p->name);
        fprintf(f, "version  = \"%s\"\n", p->version_str);
        fprintf(f, "source   = \"%s\"\n", p->source);
        fprintf(f, "checksum = \"sha256:%s\"\n", p->sha256);
        if (p->dep_count > 0) {
            fprintf(f, "\n");
            qsort(p->deps, p->dep_count, sizeof(*p->deps), compare_dep_name);
            for (size_t j = 0; j < p->dep_count; j++) {
                fprintf(f, "  [[package.dependencies]]\n");
                fprintf(f, "  name    = \"%s\"\n", p->deps[j].name);
                fprintf(f, "  version = \"%s\"\n", p->deps[j].version_str);
            }
        }
        fprintf(f, "\n");
    }
}

14. Testing Strategy

A package manager is hard to unit test because its interesting behavior is emergent. Test at multiple levels:

Unit tests:

  • Version parser (1000+ cases, including edge cases like 1.0.0-alpha.1+build.99)
  • Version constraint matching
  • SemVer comparison
  • Lockfile serialization round-trips

Resolver tests:

  • Basic diamond dependency: A→B^1, A→C^1, B→D^1, C→D^1.1 → selects D@1.1
  • Conflict detection: A→B^1, C→B^2 → error with clear message
  • Backtracking: multiple valid solutions, picks newest
  • Cycle detection (registries shouldn't have cycles, but defend anyway)

Integration tests:

Run against a local mock registry. The mock registry is a simple HTTP server serving a fixture directory of pre-made tarballs and metadata. Test:

  • Fresh install from lockfile
  • add and remove manifest changes + re-resolution
  • Cache hits on second install
  • Integrity failure detection (corrupt tarball in cache)
  • Parallel download under simulated network delay

Fuzzing:

Fuzz the manifest parser, lockfile parser, and version constraint parser. These touch untrusted input. Use libFuzzer or AFL++.

15. Performance Targets

Benchmarks that matter:

Operation Target
Cold install, 100 pkgs, good network < 10s
Warm install (all cached, hardlinks) < 500ms
Resolution only (no network) < 100ms
Startup / no-op command < 50ms
pkgman why some-pkg < 100ms

The warm install path is the most important — it runs on every git checkout, every CI build restart. Any I/O here is wasted. The target is: if the lockfile hasn't changed, install should be near-instantaneous.

Achieve this with:

  • A content-hash-keyed install stamp: store a hash of the lockfile. If it matches the current lockfile, skip installation entirely.
  • Hardlinks instead of copies
  • Skip extraction if package dir already exists and matches expected hash

16. Feature Roadmap (In Priority Order)

For a new package manager, build in this order:

  1. Version parser + constraint engine — everything depends on this
  2. Local manifest + lockfile format — define these before writing any networking code
  3. Naive resolver (backtracking) — get correct before fast
  4. Mock registry — test the full pipeline without a real server
  5. Fetcher + CAS — download, verify, cache
  6. Installer (copy-based first, hardlinks later) — atomic installs
  7. CLI skeleton — init, add, install
  8. Real registry — network, actual HTTP server
  9. PubGrub resolver — replace naive resolver, keep same interface
  10. Parallel downloads — thread pool or async
  11. Workspace support — monorepo
  12. Audit / vulnerability database
  13. Package signing + transparency log

Don't try to build a production-grade resolver and a real registry simultaneously. Start with a mock registry and a naive resolver. Both can be swapped out once the interfaces stabilize.

Appendix: Reference Implementations to Study

Package Manager Language Resolver Notes
cargo Rust PubGrub (recent) Best in class; read resolver.rs
pnpm TypeScript Custom Best node_modules layout design
pip Python Custom SAT resolvelib library, extractable
nix C++/Nix Functional Hermetic; study for reproducibility
opam OCaml CUDF/SAT Formal solver, academically grounded
apk (Alpine) C Simple Extremely fast, study for performance

Start with cargo's resolver.rs — it's well-documented, extensively tested, and uses real PubGrub semantics. The source is at src/cargo/core/resolver/ in the cargo repo.

© 2026 0xkiire.