Resolve a Package Dependency Graph with Concurrent Fetches

You are writing the dependency-resolution step of a package manager. Given one or more root packages, you must discover the full transitive dependency graph by asking a remote registry for each package's manifest. The registry is slow (tens to hundreds of milliseconds per call) and occasionally flaky, so a sequential walk takes minutes on large projects.

You are given:

def fetch(name: str) -> list[str]:
    "Returns the names of the package's direct dependencies."
    # raises TransientError  -> timeout / 5xx, may succeed on retry
    # raises NotFoundError   -> package doesn't exist, never retry

and must return:

@dataclass
class Resolution:
    deps: dict[str, list[str]]   # every successfully fetched package -> its direct deps
    failed: dict[str, str]       # package -> reason ("not found", "gave up after N attempts")
    depth: dict[str, int]        # depth assigned when the package was first discovered

Part 1: Sequential walk

Implement resolve_sequential(roots, fetch, max_retries=2, max_depth=None). Each package must be fetched successfully at most once, even though shared dependencies and cycles are common (a -> b -> a is legal in some ecosystems). A package is retried at most max_retries times after a transient error. Roots have depth 0. If max_depth is set, packages at that depth are fetched but their dependencies are not explored.

Part 2: Concurrent walk

Implement ConcurrentResolver(fetch, workers=8, max_retries=2, max_depth=None).resolve(roots) using at most workers simultaneous fetches. Requirements:

• Two workers that discover the same package at the same moment must not both fetch it.
• "Fetched successfully", "failed permanently", and "waiting for a retry" are distinct states.
• The call returns once all work is finished: the queue is empty and no fetch is still in progress (an in-progress fetch may discover new work).
• No busy-waiting, and no holding a lock while calling fetch.

Example

graph:  app  -> web, db
        web  -> http, log, ghost        (ghost does not exist)
        db   -> log, pool
        http -> log
        pool -> log
        log  -> (none)
"pool" fails transiently once.

resolve(["app"]) with 4 workers:
  deps keys -> ['app', 'db', 'http', 'log', 'pool', 'web']
  failed    -> {'ghost': 'not found'}
  pool is fetched twice (one retry), log exactly once

Constraints

• Up to 50,000 packages. The registry allows at most workers concurrent requests per client.
• Without max_depth, the set of resolved packages must be identical to the sequential version's.