ReviewOS

home-lang/home

pkg: resolve registry transitive dependencies with backtracking

#903
Closed glennmichael123 opened this 9 days ago ·
9 days ago

Parent: #884. The package resolver's Zig 0.18 collection and ownership migration covers explicitly registered graph edges and constraints. It does not make the version solver transitive.

Source-level reproduction: AdvancedDependencyResolver.resolve topologically sorts graph before choosing package versions. resolvePackage retrieves PackageRegistry.getDependencies only after selecting a version and copies those entries into ResolvedVersion.dependencies; it never adds those dependencies to the graph or constraints. Thus, if the project depends on a and the selected a version depends on b, b is absent from the returned solution unless the caller independently registered that edge. Candidate selection takes the first version satisfying the current local constraints and cannot backtrack when a later transitive constraint conflicts.

Acceptance:

  • Expand dependency closure from each selected registry version and resolve every reachable package exactly once in the final result.
  • Propagate all incoming constraints before accepting a version; backtrack or report a real conflict when version choices are incompatible.
  • Preserve deterministic version preference, explicit project-root semantics, cycle reporting, and clear ownership across retries, allocation failures, and repeated resolution.
  • Add public tests for transitive chains, diamond constraints, incompatible version branches, cycles, missing packages, and allocator-failure rollback. Run the standalone package and top-level package-manager test graphs on pinned Zig 0.17 and Zig 0.18 in Debug and ReleaseFast.

Do not count the collection/ownership migration as a completed package solver or relax dependency assertions to make the current implementation appear transitive.

9 days ago

Implemented and pushed directly to main in 4725e70 (fix(pkg): resolve transitive registry dependencies). The resolver now expands each selected registry version into the requirement set, backtracks across incompatible or cyclic candidates, reports missing transitive packages and the propagated constraints of a conflict, and returns a deterministic name-ordered solution with owned dependency metadata. Public tests cover diamond closure, late conflicting constraints, alternative missing/cyclic candidates, missing packages, registry cycles, and allocation-failure ownership/repeated resolution. Verified standalone library/check/tests and top-level package-manager tests with pinned Zig 0.17 and CI-tracked Zig 0.18 in both Debug and ReleaseFast: 35/35 tests each; all guarded runs stayed below 1.2 GB peak tree footprint. This resolves the in-memory registry solver gap described here; full Bun/runtime parity remains separately open in #66.

Sign in to comment on this issue.