`SpecializationBuilder` migration
2026-03-06
I've been working on a migration this week to change the internals of the `SpecializationBuilder` in ty. This type performs the bulk of the work when inferring a specialization when calling a generic function. We are in the middle of migrating to a new solver, which uses binary decision diagrams (BDDs) to encode the set of constraints that must collectively hold for the valid specializations.
» Theory » Binary decision diagrams
The builder currently lives in a hybrid state:
- For most types, the builder uses the "old solver" that walks formal/actual types manually, finds typevar assignments, and adds them to a simple `HashMap` that maps typevars to types. When a typevar gets multiple assignments, the old solver combines them via union. (This is correct when the typevar assignment appears in a contravariant position. But if the assignment appears in covariant position, we should use intersection.)
- For certain type variants, we use the "new solver": we create a `ConstraintSet` to represent the type mappings induced by the formal/actual types. The "hybrid" part is that for the types that use the new solver, we immediately extract solutions from the constraint set, and then add them to the same simple `HashMap` that the old solver uses.
The goal of this migration is to change the builder's internal "pending" state from the simple `HashMap` to a `ConstraintSet`, bringing us one step closer to using the new solver everywhere.
I've been dreading this part of the migration, because it requires updating several call sites that bake in deep assumptions about the internal state of `SpecializationBuilder`. I've been pleasantly surprised with how well the pi coding agent has done in putting together a detailed plan and chipping away at the implementation. I'm putting the transcripts here for posterity. Given time, I might also add some summary notes here as well.
Raw transcripts
Phase 1: Add the solution extraction hook API
Phase 2: Migrate callers to use the solution extraction hook API
Phase 3: Update callers that can make raw `ContraintSet` queries
Phase 4a: Update `preferred_type_mappings`
Phase 4b: Update final `infer_reverse` callers
Update the plan to reorder phases 5 and 6