Walk through, step by step, how a package manager builds the full dependency graph for a project once it starts from the top-level manifest - what does it actually do at each step?

## Where construction starts The construction of a dependency graph begins at a single root: your project's manifest file. That manifest lists your direct dependencies, each as a name plus a version constraint (an exact version, a range like `^2.1.0`, or a constraint expression). The resolver's job is to turn that flat list of names-and-constraints into a fully expanded, concrete graph where: - every **node** is one specific package at one specific version - every **edge** records which package needed which other package ## The traversal loop 1. **Step one** is fetching metadata for each direct dependency: the resolver asks the package registry (npm registry, Maven Central, PyPI, crates.io) or a local cache for that package's own manifest at whichever version(s) satisfy the declared constraint. That manifest is itself just another list of name/constraint pairs - the package's own dependencies. 2. **Step two** is queueing those newly discovered names as candidate nodes and repeating step one for each of them. This is a graph traversal, and different ecosystems implement it slightly differently (npm historically did something close to breadth-first with hoisting, Maven/Gradle do a form of nearest-wins resolution across a depth-first walk), but the shape is the same: keep expanding frontier nodes until fetching a package's manifest produces no dependency that isn't already accounted for. That **fixed point** - no new nodes discovered - is when the graph is "fully resolved." ## Two extra pieces of machinery Two extra pieces of machinery sit inside this loop. - **The first is deduplication**: because the same package is very often reachable through multiple paths (package A and package B might both depend on a common utility package C), the resolver has to recognize that C is the same logical dependency reached twice, not fetch and install it twice - and it has to decide which version of C satisfies both A's and B's constraints. - **The second is version constraint resolution itself**: each edge in the graph carries a range, not a pinned version, and the resolver must pick one concrete version per package (in ecosystems that require single-version resolution) or decide it's safe to install multiple versions side by side (in ecosystems like npm's `node_modules` layout that tolerate nested duplicates). This step is what produces the lockfile - `package-lock.json`, `yarn.lock`, Gradle's dependency locking, `Cargo.lock`, `poetry.lock` - a flattened, fully pinned snapshot of the graph so the expensive resolution work doesn't have to be redone (and doesn't risk producing a different answer) on every install. ## Why it is built lazily rather than declared Why build the graph this way instead of requiring every project to flatten and declare its own full dependency list? Because doing it lazily and automatically is the entire value proposition of a package manager: it lets library authors depend on other libraries without knowing or caring who will eventually consume them, and it lets consumers get a working, internally consistent set of transitive dependencies without manually chasing down every sub-dependency by hand. The cost of that convenience is that the graph-construction algorithm becomes nontrivial infrastructure in its own right - version constraint solving is related to SAT solving in the general case, which is part of why some ecosystems invest heavily in fast, correct constraint solvers, and why resolution can occasionally fail outright with "no version satisfies all constraints" errors. ## Failure modes in production The failure modes of this construction process show up in a few recognizable ways in production. - **Resolution can be slow**, because a wide, deep graph means many network round-trips to fetch manifests before the traversal reaches its fixed point - this is why lockfiles exist, to make the second and subsequent resolutions nearly instant. - **Resolution can also be nondeterministic without a lockfile**: two developers running install a week apart, with a mutable version range like `^2.1.0` in the manifest, can land on two different concrete graphs because a new matching version was published in between, producing the classic "works on my machine" bug where the actual dependency graph silently drifted. - **Resolution can fail to terminate cleanly** if two packages in the graph declare incompatible constraints on a shared transitive dependency - a distinct problem from graph construction itself, but one that only becomes visible once you understand that construction produces a graph, not a tree, and the same package name can be demanded at incompatible versions by two different paths through it. ## What the walk adds up to A concrete real-world instance: installing a single popular JavaScript framework like Next.js or a testing framework like Jest into a fresh project routinely resolves into several hundred to well over a thousand transitive packages once the recursive walk fully unfolds, which is exactly why `node_modules` directories are proverbially enormous - not because the framework itself is huge, but because the graph-construction process faithfully expanded every dependency of every dependency down to the leaves.