Building the Dependency Graph from Manifests

A package manifest is a list of names and conditions, and it is tempting to read it as a graph. It is not one. A manifest says that this package needs some version of that name satisfying a range; it does not say which version, and until that question is answered there is no edge to draw, only a fan of possibilities. The dependency graph is therefore an output of resolution as much as an input to it, and the way an ecosystem defines its nodes decides what the resolver is even allowed to look for.

Requirements are hyperedges

Take a single package at a single version. Its manifest names dependencies, and each name carries a constraint. Interpreted as a graph, that package has an edge to a set of candidate nodes rather than to one node: a hyperedge whose head is the package and whose tail is every published version of the dependency that satisfies the constraint. There may be fifty such versions or none.

Selection collapses each hyperedge into an ordinary edge. Once the resolver assigns a version to every required name, each requirement points at exactly one node, and the result is a directed graph in the usual sense. Two views of the same data are useful at different times: the hypergraph is what the search manipulates, because the tail of the hyperedge is the branching factor, and the collapsed graph is what the installer consumes, because it can be sorted, fetched, and linked.

This is why the phrase “the dependency tree” is misleading in every ecosystem that permits shared dependencies. A package required by three others is one node with three incoming edges, not three copies, and the structure is a DAG in the typical case rather than a tree. Tools that print a tree do so by duplicating the shared node under each parent, which is a rendering decision, not a statement about the graph.

Identity is name plus version plus source

A node needs an identity before a graph can have a visited set. The obvious candidate is the package name, and it is wrong for the same reason that a file’s basename is the wrong identity: two different things can share it. The working definition in most resolvers is the triple of name, version, and source — where source distinguishes a registry entry from a git URL, a local path, or an alternative registry. Two nodes with the same name and version but different sources are different nodes, and a resolver that merges them will hand the linker one artifact where it expected another.

Once source is part of identity, the number of nodes is bounded by the number of distinct (name, version, source) triples the walk reaches, not by the number of edges. This bound is what makes memoisation effective. The resolver keeps a map from identity to the manifest it fetched, and re-entering a node already on the map costs a hash lookup instead of a metadata request. In a graph with hundreds of nodes and thousands of edges, the difference between fetching per edge and fetching per node is the difference between a slow install and a tolerable one.

The identity decision also fixes what “duplicate” means. If identity is name only, a graph cannot contain two versions of one package, and any conflict must be resolved by choosing. If identity includes the version, duplicates are representable and the question becomes where to put them on disk. That single choice, discussed at length in Diamond Dependencies and Duplicate Versions, propagates into the installer, the linker, and the language’s type system.

Which edges the walk follows

Manifests usually carry several dependency sections, and they are not traversed alike. Runtime dependencies are followed transitively. Development dependencies are followed only at the root, because a dependency’s test framework is not part of what its consumers install; pulling it in would multiply the install size by the size of every package’s test suite. Build dependencies occupy a middle position: they are needed to produce an artifact, so a source-based installer follows them, while a binary installer that consumes prebuilt artifacts may not need them at all.

Optional dependencies add a third state. An edge marked optional may fail — the platform may not support the package, or its own constraints may be unsatisfiable — without failing the resolution of its parent. The graph therefore has edges whose presence is contingent, and a resolver must decide whether the contingency is evaluated before or after selection. npm’s os and cpu fields make the contingency a static property of the dependency’s metadata; a failed native build makes it a dynamic property discovered only at install time. Both exist, and they are recorded differently.

Peer dependencies are the strangest case, because the edge does not point into the dependency’s own subtree. A peer requirement constrains whichever version of a package the consumer provides at an ancestor position. It is a constraint on the solution, not a request for a node, and the graph must carry it as an annotation on the parent edge rather than as a new outgoing edge. The variants and their failure modes are set out in Peer, Optional, and Override Constraints.

Cycles are legal

Build graphs must be acyclic; package graphs need not be. Two packages can depend on each other, and this occurs legitimately when a core package exposes hooks that a companion package implements, with each naming the other. npm and Cargo tolerate the cycle at the package level, even though both reject import cycles between source files within a single build unit. The installer cannot topologically sort such a graph, so it must either condense strongly connected components and install each component as a unit, or abandon ordering and rely on the fact that installation is mostly copying files rather than executing dependent steps.

What breaks under a cycle is not installation but any algorithm that assumes a topological order. A deduplication pass that visits parents before children will loop without a visited set. A “build dependencies first” step cannot be satisfied if the cycle crosses a compilation boundary, which is why a cyclic pair usually works only when the build-time edge runs in one direction and the runtime edge in the other. The strongly connected components of the graph are the units that ordering algorithms must treat as atoms.

Cycles interact badly with version choice. In an acyclic graph, a version decision at one node cannot invalidate a decision already made above it. In a cycle, the choice at node A can change A’s dependencies, which changes the constraints reaching A through the cycle, so a naive single pass can terminate with a solution that violates its own input. The fix is the same as for any other feedback: iterate to a fixed point, or treat the whole component as a constraint problem. Minimal version selection sidesteps the issue entirely by forbidding upper bounds, so that a decision can only be revised upward and the iteration is monotone; Minimal Version Selection sets out why that terminates.

The graph is discovered during the walk

The deepest structural fact about package graphs is that their edges are a function of the version assignment. Package A at 1.0 depends on C at 1.x; at 2.0 it depends on C at 3.x and no longer on B at all. Until the resolver decides that A is 2.0, it cannot know which hyperedges to expand. Resolution is therefore not a graph traversal over a fixed structure but an interleaved process: expand a node, choose versions for its requirements, expand the results, and revise choices when a later constraint contradicts an earlier one.

This is what separates the problem from the build-graph case, where the graph is declared up front and the only question is order. Here the graph is partially known at every step, and the known part grows as decisions are made. The practical consequence for tooling is that “show me the full dependency graph” is an expensive request: it requires either a complete resolution or a traversal of the candidate hypergraph, which is larger than the resolved graph by the branching factor at every node.

Where the metadata comes from

Most registries serve a per-package document containing every published version and, for each, its dependency map. The resolver fetches one document per package name and can then read the dependency list for any version without another round trip. That design turns the network cost of exploration into one request per distinct name rather than one per candidate version, which is why resolvers can afford to consider many candidates.

The document also makes the graph’s size concrete. A registry with a few thousand popular names, each with dozens or hundreds of versions, and each version with a handful of dependencies, yields a hypergraph with far more edges than any resolved graph will contain. The resolver’s job is to cut that hypergraph down to a subgraph with exactly one version per package — or, where duplicates are allowed, a small number — and the search cost lives in the cutting, not in the reading.

from dataclasses import dataclass, field

@dataclass(frozen=True)
class NodeId:
    name: str
    version: str
    source: str = "registry"   # source is part of identity

@dataclass
class Node:
    id: NodeId
    deps: dict[str, str] = field(default_factory=dict)  # name -> range

def walk(root: Node, fetch, chosen: dict[str, str], satisfies):
    """Expand the graph using an existing assignment, tolerating cycles."""
    seen, stack, edges = set(), [root], []
    while stack:
        node = stack.pop()
        if node.id in seen:
            continue
        seen.add(node.id)
        for name, rng in node.deps.items():
            version = chosen.get(name)
            if version is None:      # unresolved: leave the hyperedge open
                continue
            if not satisfies(version, rng):
                raise ValueError((node.id, name, version, rng))
            child = fetch(name, version)
            edges.append((node.id, child.id))
            stack.append(child)
    return seen, edges

The chosen map is the interface between the search and the graph walk, and its emptiness is the reason the walk cannot be a single pass. A resolver fills it incrementally and revisits the nodes whose outgoing edges were incomplete at the time they were expanded. The bookkeeping that makes those revisits cheap — recording which decisions each open edge depends on — is the same bookkeeping that conflict-driven resolvers use to explain failures, and it is what Conflict-Driven Backtracking formalises.

Counting the cost

Two numbers frame the problem. The number of nodes is bounded by the product of the name set and the versions considered, but memoisation keeps it near the number of distinct assignments actually visited. The number of edges is bounded by the sum of dependency counts over visited nodes, which for a large application runs into the thousands while the node count stays in the hundreds.

A resolver that expands nodes without memoising, or that treats each (name, version) pair as new on every path, turns a linear walk into an exponential one. That failure mode is common enough in hand-written tooling that it is worth stating as an invariant: expansion must be keyed on node identity, and the frontier must be a set, not a stack of paths. The distinction between a graph with cycles and a graph without them then reduces to whether the visited check happens before or after the children are pushed.