From Simple to PubGrub: The Evolution of Cargo's Resolver
summary
Cargo’s resolver starts as a naive recursive backtracker that clones big state, blows the stack on dozens of deps and does exponential work (20+ needless steps) until conflict clauses are added to record why versions fail. That yields thousands of randomized tests and a SAT-based verifier, but complexity and fragility remain, so Cargo is migrating to PubGrub RS, a max-style incompatibility solver already used by Gleam and UV; it works functionally while performance and precise semantics are still being tuned.
AI-written summary · about
chapters (18)
- 0:00Introduction
- 1:31Dependency resolver basics
- 2:57First resolver in 2013
- 7:08Recursive resolver problems
- 9:55Resolver rewrite with stack
- 12:22Exponential work and errors
- 14:47Conflict clauses for failures
- 17:38Complexity and testing
- 19:21Learning from SAT solvers
- 21:50PubGrub incompatibility model
- 23:37PubGrub adoption
- 25:02Resolver future
- 25:28Q&A: Feature flags
- 27:13Q&A: SAT solver performance
- 28:40Q&A: Error messages
- 30:06Q&A: Why PubGrub
- 31:10Q&A: Correctness standards
- 32:39Q&A: Dual-resolver testing
