Skip to content

nb upgrade: false DependencyCycle from stale upstream-registry pin (webp/libtiff, missing dependency-freshness check) #359

Open
Open
nb upgrade: false DependencyCycle from stale upstream-registry pin (webp/libtiff, missing dependency-freshness check)#359

Description

@Mheaus
Mheaus
opened on Jul 24, 2026

Note from the reporter: This issue was written by Claude (an AI assistant), on behalf of and reviewed by @Mheaus, after they hit this bug while running nb upgrade and asked me to dig into it. I'm disclosing that upfront so you can weigh it accordingly. I am not opening a PR — external PRs are closed on sight per your security policy (CONTRIBUTING.md), and that's a completely reasonable policy for a package manager to have after what you described. I'm including a suggested patch + tests below purely as a time-saver in case it's useful; please treat it as a diff to read and judge, not as something to merge as-is. I had an independent review pass done on both this write-up and the patch before posting (which is how an earlier draft's flawed patch — a version that would have caused a different false-positive on any macOS formula with uses_from_macos deps, like git or pcre2 — got caught and fixed before you ever saw it), so I'm reasonably confident in what's below, but I'm still an AI describing someone else's codebase and could be wrong about something. Thank you for maintaining nanobrew — happy to answer follow-up questions or run more repros if that helps.

Summary

nb upgrade (and nb install) can report a false DependencyCycle for formulae that don't actually have a cycle in Homebrew's current dependency graph. Root cause: the verified-upstream registry pin can go stale on a formula's dependencies array without its version/revision/rebuild changing, and the freshness check that's supposed to catch staleness (formulaMetadataIsNewer in src/api/client.zig) only compares version/revision/rebuild — never the dependency list itself. So a stale pinned dependency edge silently survives the "refresh from live API" step and can combine with a fresh edge fetched for a different formula in the same resolve pass to form a cycle that doesn't exist upstream.

This is a different bug from #216 (false cycle from a mis-walked diamond dependency, already fixed) — here the input graph itself is wrong because of mixed-freshness data, not a bug in the topological sort.

Repro

$ nb upgrade
==> Checking N package(s) for updates...
==> Upgrading 9 package(s):
    ...
    libtiff (4.7.1_1 -> 4.7.2)
    libheif (1.21.2_2 -> 1.23.1)
    poppler (26.04.0 -> 26.07.0)
    ocrmypdf (17.8.0 -> 17.8.1)
    imagemagick (7.1.2-21 -> 7.1.2-27)
...
==> Resolving dependencies...
    [1ms]
nb: warning: circular dependency detected for 'libtiff', skipping
nb: libtiff: upgrade did not install 4.7.2; keeping 4.7.1_1
==> Resolving dependencies...
nb: warning: circular dependency detected for 'libheif', skipping
...

(and the same for poppler, ocrmypdf, imagemagick — all pull in libtiff/webp transitively.)

What's actually going on

nanobrew's registry/upstream.json (the "verified upstream" pinned snapshot, synced from raw.githubusercontent.com/justrach/nanobrew/main/registry/upstream.json) currently has this for webp:

{
  "token": "webp",
  "revision": 0,
  "rebuild": 0,
  "dependencies": ["giflib", "jpeg-turbo", "libpng", "libtiff"],
  "resolved": { "version": "1.6.0" }
}

But the live Homebrew API disagrees on the dependency list for that exact same version/revision/rebuild:

$ curl -s https://formulae.brew.sh/api/formula/webp.json | jq '{deps: .dependencies, version: .versions.stable, revision, rebuild: .bottle.stable.rebuild}'
{
  "deps": ["giflib", "jpeg-turbo", "libpng"],
  "version": "1.6.0",
  "revision": 0,
  "rebuild": 0
}

Homebrew dropped webp's dependency on libtiff without bumping version, revision, or bottle rebuild — so there's nothing for formulaMetadataIsNewer to notice. Meanwhile libtiff itself (fetched live, and matching the pin) depends on webp:

$ curl -s https://formulae.brew.sh/api/formula/libtiff.json | jq '.dependencies'
["jpeg-turbo", "webp", "xz", "zstd"]

So the resolver ends up with libtiff -> webp (correct, live) and webp -> libtiff (stale, from the pin) in the same graph — a cycle that doesn't exist in current Homebrew. Kahn's algorithm in src/resolve/deps.zig is behaving correctly given its input; the input itself is wrong.

I traced this through fetchFormulaWithClientAndUpstreamRegistryOptions in src/api/client.zig:

if (options.check_upstream_freshness and !tap_ref and
    !upstream_formula.revoked_fallback and upstreamFreshnessEnabled())
{
    if (fetchFormulaLive(alloc, client, name) catch null) |live| {
        if (formulaMetadataIsNewer(live, upstream_formula)) {   // <-- only version/revision/rebuild
            upstream_formula.deinit(alloc);
            return live;
        }
        live.deinit(alloc);
    }
}

It already pays for a live fetch here on every resolve (for the freshness check itself), so there's no extra network cost to also comparing dependencies — the live data is sitting right there and gets thrown away when versions match.

Suggested fix (not a PR — see note above)

The first thing I tried was a straight order-independent set-equality check between live.dependencies and upstream_formula.dependencies. That's wrong: on macOS, parseFormulaJson merges uses_from_macos into .dependencies (see the existing test "parseFormulaJson - includes uses_from_macos on macOS"), but the upstream-registry pin never does that merge — it only stores Homebrew's raw dependencies array. So live legitimately has extra entries the pin doesn't for any formula with a non-empty uses_from_macos (e.g. git, pcre2 — not obscure formulae), and a plain set-equality check would treat those as "stale" on every single resolve, defeating the pinned/verified fast path broadly rather than fixing a narrow bug.

The fix that survived review is one-directional: only treat the pin as stale when it claims a dependency that live doesn't have at all. That exactly matches the observed failure (the pin still lists libtiff, which live no longer has), and never fires on the uses_from_macos case (where live only ever has extra entries, never fewer):

--- a/src/api/client.zig
+++ b/src/api/client.zig
@@ -263,7 +263,18 @@ fn fetchFormulaWithClientAndUpstreamRegistryOptions(
                 upstreamFreshnessEnabled())
             {
                 if (fetchFormulaLive(alloc, client, name) catch null) |live| {
-                    if (formulaMetadataIsNewer(live, upstream_formula)) {
+                    // Homebrew doesn't always bump version/revision/rebuild when
+                    // only `depends_on` changes, so a pinned upstream record can
+                    // go stale on its dependency edges while formulaMetadataIsNewer
+                    // still reports "no change". That silently resurrects
+                    // dependency edges Homebrew already removed (e.g. webp no
+                    // longer depends on libtiff, but a stale pin keeps saying it
+                    // does) and can pair with an unrelated live-fetched edge in
+                    // the same graph to produce a cycle that no longer exists
+                    // upstream. Deliberately one-directional: on macOS,
+                    // parseFormulaJson merges uses_from_macos into `live`'s
+                    // .dependencies (see below) but the upstream-registry pin
+                    // never does, so `live` legitimately has extra entries the
+                    // pin doesn't — that must not be treated as staleness. Only
+                    // a pinned dependency that live *no longer has at all*
+                    // indicates the pin is out of date.
+                    if (formulaMetadataIsNewer(live, upstream_formula) or
+                        upstreamHasRemovedDependency(live, upstream_formula))
+                    {
                         upstream_formula.deinit(alloc);
                         return live;
                     }
                     live.deinit(alloc);
                 }
@@ -384,6 +395,20 @@ fn formulaMetadataIsNewer(candidate: Formula, current: Formula) bool {
         (std.mem.eql(u8, candidate_version, current_version) and candidate.rebuild > current.rebuild);
 }
 
+/// True when `upstream` lists a dependency that `live` no longer has at all —
+/// i.e. Homebrew removed a `depends_on` edge from this formula without a
+/// version/revision/rebuild bump, so the pinned upstream record is stale on
+/// its dependency graph. Intentionally one-directional: `live` legitimately
+/// contains entries `upstream` doesn't (uses_from_macos merging, see the
+/// caller), and that direction must never trigger this.
+fn upstreamHasRemovedDependency(live: Formula, upstream: Formula) bool {
+    outer: for (upstream.dependencies) |dep| {
+        for (live.dependencies) |other| {
+            if (std.mem.eql(u8, dep, other)) continue :outer;
+        }
+        return true;
+    }
+    return false;
+}
+
 /// Whether to cross-check verified-upstream pins against the live Homebrew API.
 /// On by default; set NANOBREW_DISABLE_UPSTREAM_FRESHNESS=1 to keep pins as-is
 /// (e.g. fully offline use of the embedded registry).

Tests added alongside the existing formulaMetadataIsNewer tests in src/api/client.zig:

test "upstreamHasRemovedDependency - detects a dependency the pin has but live no longer does (libtiff/webp false-cycle regression)" {
    const stale_upstream_webp = Formula{
        .name = "webp",
        .version = "1.6.0",
        .dependencies = &.{ "giflib", "jpeg-turbo", "libpng", "libtiff" },
    };
    const fresh_live_webp = Formula{
        .name = "webp",
        .version = "1.6.0",
        .dependencies = &.{ "giflib", "jpeg-turbo", "libpng" },
    };
    try testing.expect(!formulaMetadataIsNewer(fresh_live_webp, stale_upstream_webp));
    try testing.expect(upstreamHasRemovedDependency(fresh_live_webp, stale_upstream_webp));
}

test "upstreamHasRemovedDependency - does not false-positive when live has extra uses_from_macos entries" {
    const pinned_git = Formula{
        .name = "git",
        .version = "2.51.0",
        .dependencies = &.{ "pcre2", "gettext" },
    };
    const live_git_on_macos = Formula{
        .name = "git",
        .version = "2.51.0",
        .dependencies = &.{ "pcre2", "gettext", "curl", "expat" }, // uses_from_macos-merged
    };
    try testing.expect(!upstreamHasRemovedDependency(live_git_on_macos, pinned_git));
}

test "upstreamHasRemovedDependency - empty dependency lists are not stale" {
    const a = Formula{ .name = "leaf", .version = "1.0" };
    const b = Formula{ .name = "leaf", .version = "1.0" };
    try testing.expect(!upstreamHasRemovedDependency(a, b));
}

Known limitation: this is intentionally one-directional and doesn't cover the opposite case — a dependency Homebrew added to a formula without a version bump, where the pin would be missing something live has. I don't have a concrete case of that happening (unlike the removed-dependency direction, which is the actual bug being reported here), so I've left it out rather than speculatively fixing a problem I haven't observed — but flagging it in case it matters for how you want to handle this.

Verification

Ran locally against a clean checkout of main (308986a) with only src/api/client.zig modified, using the zig 0.16.0 toolchain your CI pins:

  • zig build test --summary all — before the patch: 272/273 tests passed (1 skipped). After: 275/276 tests passed (1 skipped) — the 3 new tests above, no other change, no regressions in the other 272.
  • zig build repo-checks — passes.

I didn't run the full zig build + nb install/nb upgrade end-to-end smoke test against a live macOS install (that would require building and swapping in a modified nb binary system-wide, which felt like more system-level risk than an issue report warrants) — so the unit-level fix is verified, but not an end-to-end repro-to-green on the actual nb upgrade CLI output shown above. Flagging that gap explicitly rather than implying more coverage than there is.

Environment

  • nanobrew v0.1.205 on macOS (Darwin 25.5.0, arm64)
  • Affected formulae observed: libtiff, webp, libheif, poppler, ocrmypdf, imagemagick (all transitively touch the libtiff/webp edge)
  • Reproduced independently against live formulae.brew.sh data at time of filing

Thanks for reading this far — let me know if a different fix direction (e.g. regenerating registry/upstream.json more frequently, or dropping dependency-array trust from the pin entirely) is more in line with how you want to handle staleness here. Happy to help verify a fix once you have one, if useful.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions