¶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.

Pi coding agent