Dependency Resolution & Dev Environments - SemVer, SAT vs MVS, Lockfiles, Nix Shells & Devcontainers

// Why lockfiles exist: the same manifest resolves differently on different days,
// and an integrity hash catches a tampered or swapped tarball.

function digest(s: string): string {
  // FNV-1a for the demo; real lockfiles store sha512 (npm "integrity") or sha256 (Cargo "checksum").
  let h = 0x811c9dc5;
  for (let i = 0; i < s.length; i++) { h ^= s.charCodeAt(i); h = Math.imul(h, 0x01000193) >>> 0; }
  return "fnv1a-" + h.toString(16).padStart(8, "0");
}

// Registry state on two dates for a made-up package: 4.18.0 (with a regression) was published in between.
const published: Record<string, string[]> = {
  "2026-09-01": ["4.17.0", "4.17.1"],
  "2026-10-07": ["4.17.0", "4.17.1", "4.18.0"],
};
const tarball = (ver: string) => `acme-http@${ver} contents`;

const satisfiesCaret = (ver: string, base: string) => {
  const [a, b, c] = ver.split(".").map(Number);
  const [x, y, z] = base.split(".").map(Number);
  return a === x && (b > y || (b === y && c >= z));
};
const newest = (vs: string[]) => vs.sort((p, q) => (p.localeCompare(q, undefined, { numeric: true }))).at(-1)!;

const manifest = { "acme-http": "^4.17.0" };
const base = manifest["acme-http"].slice(1);

// Without a lockfile every install re-resolves the range.
for (const day of Object.keys(published)) {
  const ver = newest(published[day].filter((x) => satisfiesCaret(x, base)));
  console.log(`no lockfile, install on ${day}: acme-http@${ver}`);
}

// With a lockfile we record the exact version and an integrity hash once.
const lock = { "acme-http": { version: "4.17.1", integrity: digest(tarball("4.17.1")) } };
console.log(`lockfile pins acme-http@${lock["acme-http"].version} ${lock["acme-http"].integrity}`);

// A later install verifies bytes against the lockfile.
function install(served: string) {
  const ok = digest(served) === lock["acme-http"].integrity;
  console.log(`  install with lockfile: ${ok ? "integrity OK" : "INTEGRITY MISMATCH, refusing to install"}`);
}
install(tarball("4.17.1"));
install("acme-http@4.17.1 contents + injected postinstall");

no lockfile, install on 2026-09-01: acme-http@4.17.1
no lockfile, install on 2026-10-07: acme-http@4.18.0
lockfile pins acme-http@4.17.1 fnv1a-e138ef85
  install with lockfile: integrity OK
  install with lockfile: INTEGRITY MISMATCH, refusing to install

"""The diamond problem under three resolution strategies.

app needs  web ^1.0 and auth ^2.0 ; both depend on the shared library 'log'.
  - newest-compatible, one copy per package (pip/uv, Poetry, Dart pub style): search with
    backtracking (a tiny SAT-like search) for ONE version of each package
  - Minimal Version Selection (Go modules, Bazel Bzlmod): take the max of declared minimums,
    no search, never newer than someone asked for
  - nested duplicates (npm/pnpm style; Cargo does this too, but only across
    semver-incompatible versions such as log 1.x vs log 2.x): each dependent may get its own copy
"""
from itertools import product

def v(s): return tuple(int(x) for x in s.split("."))

# registry: package -> version -> {dependency: (min_inclusive, max_exclusive)}
registry = {
    "web":  {"1.0.0": {"log": ("1.2.0", "2.0.0")}, "1.4.0": {"log": ("1.5.0", "2.0.0")}},
    "auth": {"2.0.0": {"log": ("1.0.0", "2.0.0")}, "2.3.0": {"log": ("2.0.0", "3.0.0")}},
    "log":  {"1.2.0": {}, "1.5.0": {}, "1.9.0": {}, "2.1.0": {}},
}
root = {"web": ("1.0.0", "2.0.0"), "auth": ("2.0.0", "3.0.0")}

def ok(ver, rng): return v(rng[0]) <= v(ver) < v(rng[1])

def newest_single():
    # Try candidate combinations, newest first; first consistent one wins (backtracking).
    names = ["web", "auth", "log"]
    cands = {n: sorted(registry[n], key=v, reverse=True) for n in names}
    tried = 0
    for combo in product(*(cands[n] for n in names)):
        tried += 1
        pick = dict(zip(names, combo))
        reqs = list(root.items()) + [(d, r) for n in ("web", "auth") for d, r in registry[n][pick[n]].items()]
        if all(ok(pick[d], r) for d, r in reqs):
            return pick, tried
    return None, tried

def mvs():
    # Each module lists MINIMUM versions; build list = max of the minimums, no upper bounds.
    pick = {"web": root["web"][0], "auth": root["auth"][0]}
    mins = [registry[n][pick[n]]["log"][0] for n in ("web", "auth")]
    pick["log"] = max(mins, key=v)
    return pick

def nested():
    # Newest of each, and every dependent resolves its own 'log' independently.
    pick = {n: max((x for x in registry[n] if ok(x, root[n])), key=v) for n in root}
    copies = {f"log (for {n})": max((x for x in registry["log"] if ok(x, registry[n][pick[n]]["log"])), key=v) for n in pick}
    return pick, copies

pick, tried = newest_single()
print("newest-compatible single copy:", pick, f"(after {tried} candidate combos)")
print("minimal version selection:   ", mvs())
p, copies = nested()
print("nested duplicates:           ", p, copies)
print("note: auth 2.3.0 wants log 2.x, web wants log 1.x; one-copy resolvers must backtrack to auth 2.0.0")

newest-compatible single copy: {'web': '1.4.0', 'auth': '2.0.0', 'log': '1.9.0'} (after 6 candidate combos)
minimal version selection:    {'web': '1.0.0', 'auth': '2.0.0', 'log': '1.2.0'}
nested duplicates:            {'web': '1.4.0', 'auth': '2.3.0'} {'log (for web)': '1.9.0', 'log (for auth)': '2.1.0'}
note: auth 2.3.0 wants log 2.x, web wants log 1.x; one-copy resolvers must backtrack to auth 2.0.0