Faster constraint solving

[jorenham]

The explanation of constraint solving algorithm in #9896 (comment) made me wonder about ways that the amount of generated constraint sets could be reduced.

Perhaps your confusion stems from an incomplete understanding of constraint solving, which is performed when evaluating a call to a generic function. Here's a simplified explanation of the three-step process:

1. Collect constraints. This is done by comparing the argument and parameter types. This typically results in a single constraint set, but it can produce multiple constraint sets if overloads are present. Every overload multiplies the number of constraint sets by the number of applicable overloads that it supplies. For example, if a protocol defines two overloaded methods each with three applicable overloads each, there will be nine total constraint sets generated. These have no particular order associated with them. A constraint does not necessarily correspond to a single overload; it might come from a combination of multiple overloads.
2. Solve the constraints for each of the constraint sets. If any of the constraint sets are unsolvable, eliminate them from the running. If there are no solvable constraint sets remaining, report an error to the user.
3. If one or more constraint sets are solvable, use the solved values to specialize the return type. If the return type includes a Callable that is parameterized with a ParamSpec, synthesize an overloaded callable with each constraint set contributing a separate overload signature. If a type variable is not a ParamSpec (i.e. it's a simple TypeVar or TypeVarTuple) or it's a ParamSpec that is used outside of a Callable, apply the solutions from all remaining constraint sets. The final specialized return type must accommodate all of the remaining constraint sets, so the resulting type will need to be a union of all of the solutions from the various constraint sets.

So the size of a particular constraint set matches the size of the generic members of a protocol, and in case of an overloaded method, this is a single overload. And for each possible combination of overloads, there is a constraint sets. So there are O(n^m) csets for m with n overloads each, and O(m n^m) constraints in total. I think it's safe to say that we're dealing with a combinatorial explosion of collected constraints, so the bottleneck lies within step 1.

I thought of several ways that could reduce the amount of generated constraints in certain scenarios. In the worst-case scenario (big-O), these will be equivalent to the current implementation. But as far as I'm aware, the current worst-case no. of collected constraints is exactly the same as in the best-case scenario. It's this best-case scenario (little-o notation) is what these approaches aim to reduce.

Perhaps I'm reinventing the wheel here, and it's probably way more difficult to implement this than I'm currently imagining it would be, but on the off-chance that it could help I thought I might as well share it 🤷🏻.

Methods with identical overloaded signatures

From experience I know that protocols often have methods with identical overloaded signatures, e.g. __{lt,le,ge,gt}__ have in many cases the same signature, and it's not uncommon for protocols to have at least two of those. If for instance you have a protocol with all 4 of them, and they have 2 overloads each, then currently, you'd get 2**4 == 16 constraint sets. But if you don't consider them as individual methods, but as a set of overloaded signatures, then the order of the constraint sets shrinks from 4 to 1, and the amount of constraint sets will be 2**1 == 2.

Identical individual overload signatures

The previous approach deduplicates the amount of methods, which requires methods to have the amount of overloads, each of which are pairwise identical in their signature. But there will also be cases where one method will only a subset of its overloads identical to those of another method.
While collecting the constraints, you could collect a "overload signature -> constraint" mapping. If you encounter an overload whose signature already exists in that mapping, the instead of generating a new constraint, you generate a "reference constraint" to the existing one. This way, solving one constraint, will solve all the reference to it as well.
This won't reduce the literal amount of generated constraints, but if will reduce the amount of constraints that need to be solved, let's call them the "effective constraints".

Because this works in the level of individual constraints (not constraint sets), this could also be beneficial in the non-overloaded setting, i.e. a single constraint set of which at least two constraints correspond the identical signatures.

Early constraint solving

If you have three methods with two overloads each, you'll end up with 2**3 == 8 constraint sets. But if the first overload of the first method is unsolvable, then it the amount of constraint sets reduces to 2**2 = 4. By solving a single constraint early during collection, we avoided having to check 4 constraint sets of 3 constraints each.
By memoizing/caching the solved constraints, or using the "reference constraints" in the previous approach, this won't be (much) slower than it currently is in the worst-case scenario. In all other scenarios, the speedup will be exponential in the no. of unsolvable constraints.

[erictraut]

Yes, it's way more complicated than you're assuming.

The overview of the constraint solving process that I provided in the other thread was intentionally simplified, and it omits a bunch of additional complexities and heuristics involved in the process.

[jorenham]

Yes, it's way more complicated than you're assuming.

That's why I said

it's probably way more difficult to implement this than I'm currently imagining it would be

---

Anyway, I'm just trying to help out; do with it what you want 🤷🏻